fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <cmath>
  5. #include <unordered_map>
  6.  
  7. using namespace std;
  8.  
  9. int solution(string &S, string &T) {
  10.     int n = S.length();
  11.     unordered_map<int, int> pos_diff; // Tracks positive differences
  12.     unordered_map<int, int> neg_diff; // Tracks negative differences
  13.  
  14.     // Collect all mismatches
  15.     for (int i = 0; i < n; ++i) {
  16.         int diff = S[i] - T[i];
  17.         if (diff > 0) pos_diff[diff]++;
  18.         else if (diff < 0) neg_diff[-diff]++;
  19.     }
  20.  
  21.     int swaps = 0;
  22.  
  23.     // Match pairs of differences to cancel out mismatches with minimal swaps
  24.     for (auto &p : pos_diff) {
  25.         int diff_value = p.first;
  26.         int pos_count = p.second;
  27.  
  28.         if (neg_diff.find(diff_value) != neg_diff.end()) {
  29.             int neg_count = neg_diff[diff_value];
  30.             int matches = min(pos_count, neg_count);
  31.             swaps += matches;
  32.             pos_diff[diff_value] -= matches;
  33.             neg_diff[diff_value] -= matches;
  34.         }
  35.     }
  36.  
  37.     // Count remaining mismatches, which need two swaps each
  38.     int remaining_mismatches = 0;
  39.     for (auto &p : pos_diff) remaining_mismatches += p.second;
  40.     for (auto &p : neg_diff) remaining_mismatches += p.second;
  41.  
  42.     swaps += remaining_mismatches / 2;
  43.  
  44.     return swaps;
  45. }
  46.  
  47. int main() {
  48.     string S = "29162";
  49.     string T = "10524";
  50.     std::cout << "Minimum number of swaps: " << solution(S, T) << std::endl;
  51.     return 0;
  52. }
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Minimum number of swaps: 2
https://ideone.com/iHbWqq
language:
C++ (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!