aboutsummaryrefslogtreecommitdiff
path: root/smallest_string_swaps.cpp
blob: c5213092b2e7520a73f203f6ba809f24f700ecc5 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include "leetcode.h"

class Solution {
public:
  vector<int> parent;
  string smallestStringWithSwaps(string s, vector<vector<int>> &pairs) {
    parent.resize(s.length());
    map<int, set<int>> obj;
    set<int> idx;
    string ans = s;
    for (int i = 0; i < parent.size(); i++)
      parent[i] = i;
    for (int i = 0; i < pairs.size(); i++) {
      int u = pairs[i][0];
      int v = pairs[i][1];
      int fx = findParent(u);
      int fy = findParent(v);
      if (fx != fy)
        parent[fy] = fx;
    }
    for (int i = 0; i < pairs.size(); i++) {
      int u = pairs[i][0];
      int v = pairs[i][1];
      int fx = findParent(u);
      obj[fx].insert(u);
      obj[fx].insert(v);
    }
    for (auto it = obj.begin(); it != obj.end(); it++) {
      idx = it->second;
      vector<pair<char, int>> t;
      auto index = idx.begin();
      for (index = idx.begin(); index != idx.end(); index++) {
        int pos = *index;
        char ch = s[pos];
        t.push_back({ch, pos});
      }
      sort(t.begin(), t.end());
      index = idx.begin();
      for (int i = 0; i < t.size(); i++) {
        ans[*index] = t[i].first;
        index++;
      }
    }
    return ans;
  }

private:
  int findParent(int n) {
    if (parent[n] == n)
      return n;
    return parent[n] = findParent(parent[n]);
  }
};

int main() {}