Problem Statement
You have a string S.
You are allowed to make some swaps. The allowed swaps are described by the int[]s A and B. For each i, you are allowed to swap the characters that are at (0-based) indices A[i] and B[i] in the string S.
You may perform the allowed swaps in any order, and you may perform each of them arbitrarily many times.
Return the lexicographically smallest string you can obtain.
Definition
- Class:
- RestrictedSwaps
- Method:
- rearrange
- Parameters:
- String, int[], int[]
- Returns:
- String
- Method signature:
- String rearrange(String S, int[] A, int[] B)
- (be sure your method is public)
Notes
- Given two distinct strings X and Y of the same length, the lexicographically smaller one is the one that has a character with the smaller ASCII value at the smallest index at which they differ.
- For example, "pocket" < "potato" because both start with 'p', both continue with 'o', and at index 2 we have 'c' < 't'.
Constraints
- S will have between 1 and 2500 characters, inclusive.
- Each character in S will be a lowercase English letter ('a'-'z').
- A will have between 0 and 300 elements, inclusive.
- B will have the same number of elements as A.
- Each number in A and B will be between 0 and length(S)-1, inclusive.
Examples
"topcoder"
{0, 1, 2, 3, 4, 5, 6}{1, 2, 3, 4, 5, 6, 7}Returns: "cdeooprt"
You can swap any pair of consecutive characters in S. This allows us to use bubble sort to arrange the entire string S into non-descending order."topcoder"
{4, 4, 7, 4}{4, 4, 7, 1}Returns: "topcoder"
Here all you may do is useless: swapping a character with itself doesn't change the string at all, and swapping the two 'o's doesn't do much either."topcoder"
{0, 2, 3, 5}{4, 6, 7, 1}Returns: "odectopr"
"acb"
{0, 0}{1, 2}Returns: "abc"
Currently, the first swap doesn't improve the current string: it changes it to "cab". The second swap doesn't improve the current string either: it changes it to "bca". Still, we can use these swaps to improve the current string: if we do the first swap, then the second swap, and then the first swap again, the string will change as follows: "acb" -> "cab" -> "bac" -> "abc".