SurprisingStrings | Topcoder Archive

Problem Statement

A string is called surprising if there are no two symbols x and y of the alphabet such that there are two pairs of occurrences of these symbols where x precedes y by the same distance. For instance, the string "ABCBACC" is not surprising since there are two occasions where the symbol 'A' precedes the symbol 'C' by the distance two. Likewise "ABACA" is not surprising (overlaps count, so here, 'A' precedes 'A' twice by two symbols), while "ABACB" is a surprising string.

Two surprising strings are considered equivalent if one is an isomorphism (see notes) of the other. Only the lexicographically first of these will be considered. For instance, "AABA" and "CCEC" are equivalent, and since "AABA" is the lexicographically first of these, "CCEC" will not be counted. In this task the alphabet will always use uppercase letters as the symbols, starting with 'A', 'B', etc. If we consider all surprising strings containing at most alphabetSize different symbols, and sort them lexicographically, we would get the list (when alphabetSize is 3)

{ "A", "AA", "AAB", "AABA", "AABAC", "AABC", "AABCA", "AABCAC", ... }

Create a class SurprisingStrings containing the method getString which takes an int alphabetSize, the number of different symbols in the alphabet, and an int index. The method should return the index'th surprising string in the ordered list of surprising strings of the given alphabet size. The first string in the list has index 1.

Definition

Class:: SurprisingStrings
Method:: getString
Parameters:: int, int
Returns:: String
Method signature:: String getString(int alphabetSize, int index)
(be sure your method is public)

Notes

Hint: An alphabet with 7 symbols has less than 1,000,000 distinct surprising strings.
A string is an isomorphism of another string if there exists a one-to-one mapping of symbols so that the first string maps to the second string. The string "CCEC" is an isomorphism to "AABA" because of the mapping 'A'<->'C', 'B'<->'E'. "ABC" is not an isomorphism of "ACC" because the mapping 'A'<->'A', 'B'<->'C', 'C'<->'C' is not one-to-one.

Constraints

alphabetSize will be between 1 and 7, inclusive.
index will be between 1 and the maximum number of distinct surprising strings in the given alphabet, inclusive.

Examples

```
3
```
```
8
```
```
Returns: "AABCAC"
```
The eight first surprising strings are listed in the problem statement above.
```
5
```
```
1
```
```
Returns: "A"
```
```
4
```
```
35
```
```
Returns: "AABCDBD"
```

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.