String Sorting

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
3 upvotes
Asked in companies
FacebookHCL TechnologiesAmazon

Problem statement

You and your friend found a string ‘S’ of length ‘N’. You love to rearrange the strings, So you decided to rearrange this string too. But this time, your friend puts a constraint on rearranging. He gave you ‘M’ pairs of integers, each pair denoting two indices of the string ‘S’. He also gave you an operation. In one operation, you can select a pair of indices from the given ‘M’ pairs and swap the character present at those indices in the string.

Your task is to rearrange the strings following the given constraints and find the lexicographically smallest string that you can obtain by doing the operations any number of times (might be 0 as well).

Detailed explanation ( Input/output format, Notes, Images )
Input Format- 
First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains an integer ‘N’, denoting the length of the String.
The following line contains the string ‘S’ of the length ‘N’.
The following line contains an integer ‘M’, denoting the number of pairs.
The following ‘M’ line contains two space-separated integers, denoting the pair of indices.
Output Format- 
For each test case, print the lexicographically smallest string that you can make after rearranging the string ‘S’.
Constraints - 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
1 <= ‘M’ <= 10^5
1 <= Pair[i][0], Pair[i][1] <= ‘N’  i ∈  (1,M)
Note-sum of ‘N’ and ‘M’ over all test cases does not exceed 10^5, respectively.

Time Limit: 1 sec
Sample Input-1
2
4
dcab
2
1 4
2 3
3
cba
2
1 2
2 3
Sample Output-1
bacd
abc
Explanation for Sample Input 1:
For test case 1:
    Swapping S[1] and S[4], S becomes “bcad”.
    Swapping S[2] and S[3], S becomes “bacd”.
For test case 2:
    Swapping S[1] and S[2], S becomes “bca”.
    Swapping S[2] and S[3], S becomes “bac”.
    Swapping S[1] and S[2], S becomes “abc”.
Sample Input -2
2
4
dcab
3
1 4
2 3
1 3
4
dcba
3
1 2
2 3
3 4
Sample Output -2
abcd
abcd
Hint

Can we consider the indices as graph’s nodes?

Approaches (1)
DFS

Approach: We will consider the indices as the graph’s nodes and all the pairs as the edges connecting the given indices/nodes. The problem comes down to finding all the connected components of the undirected graph that we just formed.

We then want to look at the characters associated with those indices in the connected components. Sort these characters and place them in ascending order in the index. We will do this for all the connected components and then assign them back to a string and print the string.

 

Algorithm: 

  • Func dfs(cur, graph, visited, ans):
    • Iterate in all the children of node ‘cur’.
      • If visited[child] == 0:
        • Update visited[child] to 1.
        • Append child to ‘ans’.
        • Call the dfs(child, graph, visited, ans).
  • Func Main():
    • Create a 2D vector, ‘graph’ of length ‘N + 1’.
    • Create an array, ‘visited’ of length ‘N + 1’ and initialize all its values to 0.
    • Iterate in all the pairs.
      • Append Pair[i][1] to graph[Pair[i][0]].
      • Append Pair[i][0] to graph[Pair[i][1]].
    • Iterate using a for loop from i = ‘1’ to ‘N’.
      • If visited[i] == 0:
        • Update visited[i] to 1
        • Create a vector ‘ans’.
        • Append ’i’ to ‘ans’.
        • Call the dfs(i, graph, visited, ans).
        • Sort ‘ans’.
        • Create a vector ‘chars.’
        • Iterate in ans.
          • Append S[j - 1] in ‘chars’.
        • Sort ‘chars’.
        • Iterate using a for loop from j = ‘0’ to ans.size().
          • Update S[ans[j] - 1] to chars[j].
    • Print ‘S’.
Time Complexity

O(N * log(N)), Where N is the number of nodes in the graph.

 

We are sorting two vectors. Hence the overall complexity is O(N * log(N)).

Space Complexity

O(N + M), where N is the number of nodes and M is the number of edges.

 

We are creating a 2D array of length ‘N’ to store the graph’s ‘M’ edges. Hence the overall complexity is O(N + M).

Code Solution
(100% EXP penalty)
String Sorting
Full screen
Console