1202. Smallest String With Swaps LeetCode Solution

In this guide, you will get 1202. Smallest String With Swaps LeetCode Solution with the best time and space complexity. The solution to Smallest String With Swaps problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Smallest String With Swaps solution in C++
Smallest String With Swaps solution in Java
Smallest String With Swaps solution in Python
Additional Resources

1202. Smallest String With Swaps LeetCode Solution image

Problem Statement of Smallest String With Swaps

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.
You can swap the characters at any pair of indices in the given pairs any number of times.
Return the lexicographically smallest string that s can be changed to after using the swaps.

Example 1:

Input: s = “dcab”, pairs = [[0,3],[1,2]]
Output: “bacd”
Explaination:
Swap s[0] and s[3], s = “bcad”
Swap s[1] and s[2], s = “bacd”

Example 2:

Input: s = “dcab”, pairs = [[0,3],[1,2],[0,2]]
Output: “abcd”
Explaination:
Swap s[0] and s[3], s = “bcad”
Swap s[0] and s[2], s = “acbd”
Swap s[1] and s[2], s = “abcd”
Example 3:

Input: s = “cba”, pairs = [[0,1],[1,2]]
Output: “abc”
Explaination:
Swap s[0] and s[1], s = “bca”
Swap s[1] and s[2], s = “bac”
Swap s[0] and s[1], s = “abc”

Constraints:

1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s only contains lower case English letters.

Complexity Analysis

Time Complexity: O(n\log^* n + \texttt{sort}(\texttt{s}))
Space Complexity: O(n)

1202. Smallest String With Swaps LeetCode Solution in C++

class UnionFind {
 public:
  UnionFind(int n) : id(n), rank(n) {
    iota(id.begin(), id.end(), 0);
  }

  void unionByRank(int u, int v) {
    const int i = find(u);
    const int j = find(v);
    if (i == j)
      return;
    if (rank[i] < rank[j]) {
      id[i] = j;
    } else if (rank[i] > rank[j]) {
      id[j] = i;
    } else {
      id[i] = j;
      ++rank[j];
    }
  }

  int find(int u) {
    return id[u] == u ? u : id[u] = find(id[u]);
  }

 private:
  vector<int> id;
  vector<int> rank;
};

class Solution {
 public:
  string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
    string ans;
    UnionFind uf(s.length());
    unordered_map<int, priority_queue<char, vector<char>, greater<>>>
        indexToLetters;

    for (const vector<int>& pair : pairs) {
      const int a = pair[0];
      const int b = pair[1];
      uf.unionByRank(a, b);
    }

    for (int i = 0; i < s.length(); ++i)
      indexToLetters[uf.find(i)].push(s[i]);

    for (int i = 0; i < s.length(); ++i)
      ans += indexToLetters[uf.find(i)].top(), indexToLetters[uf.find(i)].pop();

    return ans;
  }
};
/* code provided by PROGIEZ */

1202. Smallest String With Swaps LeetCode Solution in Java

class UnionFind {
  public UnionFind(int n) {
    id = new int[n];
    rank = new int[n];
    for (int i = 0; i < n; ++i)
      id[i] = i;
  }

  public void unionByRank(int u, int v) {
    final int i = find(u);
    final int j = find(v);
    if (i == j)
      return;
    if (rank[i] < rank[j]) {
      id[i] = j;
    } else if (rank[i] > rank[j]) {
      id[j] = i;
    } else {
      id[i] = j;
      ++rank[j];
    }
  }

  public int find(int u) {
    return id[u] == u ? u : (id[u] = find(id[u]));
  }

  private int[] id;
  private int[] rank;
}

class Solution {
  public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
    StringBuilder sb = new StringBuilder();
    UnionFind uf = new UnionFind(s.length());
    Map<Integer, Queue<Character>> indexToLetters = new HashMap<>();

    for (List<Integer> pair : pairs) {
      final int a = pair.get(0);
      final int b = pair.get(1);
      uf.unionByRank(a, b);
    }

    for (int i = 0; i < s.length(); ++i)
      indexToLetters.computeIfAbsent(uf.find(i), k -> new PriorityQueue<>()).offer(s.charAt(i));

    for (int i = 0; i < s.length(); ++i)
      sb.append(indexToLetters.get(uf.find(i)).poll());

    return sb.toString();
  }
}
// code provided by PROGIEZ

1202. Smallest String With Swaps LeetCode Solution in Python

class UnionFind:
  def __init__(self, n: int):
    self.id = list(range(n))
    self.rank = [0] * n

  def unionByRank(self, u: int, v: int) -> None:
    i = self.find(u)
    j = self.find(v)
    if i == j:
      return
    if self.rank[i] < self.rank[j]:
      self.id[i] = j
    elif self.rank[i] > self.rank[j]:
      self.id[j] = i
    else:
      self.id[i] = j
      self.rank[j] += 1

  def find(self, u: int) -> int:
    if self.id[u] != u:
      self.id[u] = self.find(self.id[u])
    return self.id[u]


class Solution:
  def smallestStringWithSwaps(self, s: str, pairs: list[list[int]]) -> str:
    uf = UnionFind(len(s))
    indexToLetters = collections.defaultdict(list)

    for a, b in pairs:
      uf.unionByRank(a, b)

    for i, c in enumerate(s):
      indexToLetters[uf.find(i)].append(c)

    for key in indexToLetters.keys():
      indexToLetters[key].sort(reverse=True)

    return ''.join(indexToLetters[uf.find(i)].pop()
                   for i in range(len(s)))
 # code by PROGIEZ