Last Updated: 2 Nov, 2021

String Sorting

Moderate

Asked in companies

Solve now

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).

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

Solve now

Approaches

01 Approach

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’.

Solve now