SwapSort | Topcoder Archive

Problem Statement

Given a string of distinct letters, sort them into ascending order by doing a sequence of swaps, where each swap can interchange any two of the letters.

Create a class SwapSort that contains a method swaps that is given a String letters and that returns a String showing the shortest sequence of swaps which will sort letters. Each swap in the returned sequence should be shown as the two letters being swapped, and adjacent swaps should be separated by a single comma (',').

If there is more than one minimal swap sequence, return the one that comes first lexicographically (in the ASCII ordering).

Definition

Class:: SwapSort
Method:: swaps
Parameters:: String
Returns:: String
Method signature:: String swaps(String letters)
(be sure your method is public)

Constraints

letters will contain between 1 and 50 letters 'A'-'Z' or 'a'-'z', inclusive.
The characters in letters will be distinct.

Examples

```
"ABCED"
```
```
Returns: "DE"
```
This can be sorted with a single swap. Of course "ED" would be another way of expressing this swap, but "DE" comes earlier alphabetically.
```
"axrA"
```
```
Returns: "Aa,ax"
```
We must sort these into "Aarx". After swapping 'A' and 'a', "axrA" has become "Axra" and we can complete the sort by then swapping the 'x' with the 'a'.

"problematic"

Returns: "ac,ap,be,bi,br,co,il,pt"

"abcdefABCDEF"

Returns: "Aa,Bb,Cc,Dd,Ee,Ff"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.