aboutsummaryrefslogtreecommitdiff
path: root/smallest_string_swaps.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'smallest_string_swaps.cpp')
-rw-r--r--smallest_string_swaps.cpp55
1 files changed, 55 insertions, 0 deletions
diff --git a/smallest_string_swaps.cpp b/smallest_string_swaps.cpp
new file mode 100644
index 0000000..c521309
--- /dev/null
+++ b/smallest_string_swaps.cpp
@@ -0,0 +1,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() {}