Leetcode 1202: Smallest String With Swaps
You are given a string s and an array of pairs of indices pairs where each pair pairs[i] = [a, b] represents two indices in the string. You can swap the characters at any of these index pairs any number of times. Your task is to return the lexicographically smallest string that can be obtained after performing the swaps.
Problem
Approach
Steps
Complexity
Input: You are given a string s and a 2D array pairs where each pair represents two indices in the string that can be swapped.
Example: Input: s = "zaxy", pairs = [[0,3],[1,2]]
Constraints:
• 1 <= s.length <= 10^5
• 0 <= pairs.length <= 10^5
• 0 <= pairs[i][0], pairs[i][1] < s.length
• s only contains lowercase English letters.
Output: Return the lexicographically smallest string that can be obtained by swapping the characters at the given pairs of indices.
Example: Output: "axyz"
Constraints:
Goal: The goal is to find the lexicographically smallest string by performing the allowed swaps.
Steps:
• Use Union-Find (Disjoint Set Union) to group indices that can be connected through the given pairs.
• For each group, sort the indices and the characters in those positions.
• Assign the sorted characters back to the indices to form the smallest possible string.
Goal: The problem has constraints to ensure that the input size is manageable.
Steps:
• 1 <= s.length <= 10^5
• 0 <= pairs.length <= 10^5
• 0 <= pairs[i][0], pairs[i][1] < s.length
• s only contains lowercase English letters.
Assumptions:
• It is assumed that the input string s only contains lowercase English letters.
• Input: Input: s = "zaxy", pairs = [[0,3],[1,2]]
• Explanation: Swap s[0] and s[3], s = "yazx". Swap s[1] and s[2], s = "axyz".
• Input: Input: s = "xyza", pairs = [[0,3],[1,2],[0,2]]
• Explanation: Swap s[0] and s[3], s = "ayzx". Swap s[0] and s[2], s = "axyz".
• Input: Input: s = "acdb", pairs = [[0,1],[1,2],[2,3]]
• Explanation: Swap s[0] and s[1], s = "cabd". Swap s[1] and s[2], s = "cdab". Swap s[2] and s[3], s = "abcd".
Approach: To solve this problem efficiently, we use a Union-Find data structure to group indices that can be swapped and then sort the characters in those groups.
Observations:
• Union-Find allows us to efficiently group indices that can be swapped together.
• Sorting the characters within each group gives the lexicographically smallest arrangement.
• The solution can be broken down into finding connected components and sorting them to get the smallest string.
Steps:
• Use Union-Find to identify groups of indices that can be swapped.
• For each group, extract the characters from those indices and sort them.
• Place the sorted characters back in the positions of their corresponding indices in the original string.
Empty Inputs:
• Ensure the string is not empty, as this case is out of bounds based on the problem constraints.
Large Inputs:
• Make sure the solution is efficient enough to handle large inputs (strings and pairs up to 10^5 in length).
Special Values:
• Handle cases where all indices are part of the same group or no indices can be swapped.
Constraints:
• The solution must account for up to 10^5 indices and swap pairs efficiently.
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = s.size();
UF uf = UF(n);
for(vector<int> each: pairs)
uf.join(each[0], each[1]);
vector<vector<int>> grps = uf.pairs();
vector<char> ans(n, '-');
for(vector<int> grp : grps) {
sort(grp.begin(), grp.end());
vector<char> chr;
for(int g : grp) chr.push_back(s[g]);
sort(chr.begin(), chr.end(), [](unsigned char c1, unsigned char c2){ return std::tolower(c1) < std::tolower(c2); });
int i = 0;
for(int x: grp)
ans[x] = chr[i++];
}
string ret(ans.begin(), ans.end());
return ret;
}
1 : Function Definition
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
Define the function `smallestStringWithSwaps` which takes a string `s` and a list of index pairs `pairs`. The goal is to sort the characters of `s` based on these index pairs, ensuring that the swaps respect the connected components defined by the pairs.
2 : Variable Initialization
int n = s.size();
Store the length of the input string `s` in the variable `n`.
3 : Union-Find Initialization
UF uf = UF(n);
Initialize a union-find data structure `uf` with `n` elements to manage the connected components of the indices.
4 : Loop Through Pairs
for(vector<int> each: pairs)
Loop through each pair in the `pairs` vector, representing index pairs that can be swapped.
5 : Union-Find Operation
uf.join(each[0], each[1]);
For each pair, join the two indices into the same connected component using the union-find `join` operation.
6 : Empty Line
Empty line for readability, separating sections of code.
7 : Union-Find Result
vector<vector<int>> grps = uf.pairs();
Get the connected components from the union-find data structure and store them in the vector `grps`.
8 : Vector Initialization
vector<char> ans(n, '-');
Initialize a vector `ans` of size `n`, filled with `'-'`, to store the result after sorting and swapping characters.
9 : Loop Through Groups
for(vector<int> grp : grps) {
Iterate through each group of connected indices in `grps` to sort the characters in those positions.
10 : Sorting Indices
sort(grp.begin(), grp.end());
Sort the indices in the current group to arrange them in ascending order.
11 : Character Vector Initialization
vector<char> chr;
Initialize an empty vector `chr` to store the characters corresponding to the current group of indices.
12 : Fill Character Vector
for(int g : grp) chr.push_back(s[g]);
Push the characters from the string `s` corresponding to the current group of indices into the vector `chr`.
13 : Character Sorting
sort(chr.begin(), chr.end(), [](unsigned char c1, unsigned char c2){ return std::tolower(c1) < std::tolower(c2); });
Sort the characters in `chr` lexicographically, ignoring case, to ensure case-insensitive sorting.
14 : Character Assignment
int i = 0;
Initialize an index `i` to keep track of the position in the sorted character vector `chr`.
15 : Assign Sorted Characters
for(int x: grp)
For each index `x` in the current group `grp`, assign the corresponding character from `chr` to the result vector `ans`.
16 : Assign Character from Sorted List
ans[x] = chr[i++];
Assign the character at position `i` from the sorted `chr` vector to the corresponding position `x` in the result vector `ans`, and increment `i`.
17 : Convert to String
string ret(ans.begin(), ans.end());
Convert the result vector `ans` into a string `ret`.
18 : Return Statement
return ret;
Return the final string `ret` which is the result of the character swaps and sorting.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The Union-Find operations take near constant time, and sorting the groups takes O(n log n).
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the space needed for the Union-Find structure and the character arrays.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus