Connection Status:
Competition Arena > RestrictedSwaps

RestrictedSwaps

2021 Regional 2 · 2021-04-13 · by misof

2021 Regional 2 · 2021-04-13 · by misof · Graph Theory, Sorting
Class Name: RestrictedSwaps
Return Type: String
Method Name: rearrange
Arg Types: (string, vector<int>, vector<int>)
Problem Statement

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.

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

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

2)
"topcoder"
{0, 2, 3, 5}
{4, 6, 7, 1}
Returns: "odectopr"
3)
"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".

4)
"z"
{}
{}
Returns: "z"

Submissions are judged against all 32 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RestrictedSwaps with a public method string rearrange(string S, vector<int> A, vector<int> B) · 32 test cases · 2 s / 256 MB per case

Submitting as anonymous