Permutation | Topcoder Archive

Problem Statement

A permutation of the letters in an alphabet can be described by a string that contains each letter exactly once. For example, CABD describes the permutation of ABCD that maps A to C, B to A, C to B, and D to D. If we repeatedly apply that permutation, we will get the sequence ABCD,CABD,BCAD,ABCD,CABD,BCAD,ABCD,... This permutation is cyclic with length 3.

We want to find the permutation of the first n letters of

    ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz

that has the longest cycle. Create a class Permutation that contains the method best that takes the number of characters n as input and returns the lexicographically first permutation that has the maximum possible cycle length.

"Lexicographically first" means the String that would sort first among all the permutations of maximum cycle length, using the ASCII sequence (which sorts uppercase letters before lowercase letters).

Definition

Class:: Permutation
Method:: best
Parameters:: int
Returns:: String
Method signature:: String best(int n)
(be sure your method is public)

Constraints

n is between 1 and 52 inclusive

Examples

```
6
```
```
Returns: "ACBEFD"
```
This permutation has cycle length 6. So does BDEFCA, but ACBEFD is lexicographically first. The cycle is: ABCDEF -> ACBEFD -> ABCFDE -> ACBDEF -> ABCEFD -> ACBFDE -> ABCDEF
```
7
```
```
Returns: "BCAEFGD"
```
This is the lexicographically first permutation with cycle length 12

Returns: "BCDEAGHIJKLFNOPQRSTMVWXYZabcU"

```
1
```
```
Returns: "A"
```
```
8
```
```
Returns: "BCAEFGHD"
```

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.