UnrepeatableWords | Topcoder Archive

Problem Statement

For a given integer k, we call a string S k-unrepeatable if there is no substring that appears k consecutive times in S.

For example, the string CCABAABAABAC is 4-unrepeatable. But it's not 3-unrepeatable, because the string ABA appears in it 3 times in a row. CCABAABACABA and ABABAABA are examples of 3-unrepeatable strings.

You are given three integers, k, n and allowed. Return the lexicographically smallest k-unrepeatable word of length n that uses only the first allowed uppercase characters of the English alphabet. If no such word exists, return the empty string.

Definition

Class:: UnrepeatableWords
Method:: getWord
Parameters:: int, int, int
Returns:: String
Method signature:: String getWord(int k, int n, int allowed)
(be sure your method is public)

Constraints

k will be between 2 and 10, inclusive.
n will be between 1 and 50, inclusive.
allowed will be between 1 and 26, inclusive.

Examples

```
3
```
```
5
```
```
2
```
```
Returns: "AABAA"
```
All lexicographically smaller strings of length 5 contain three consecutive occurrences of the letter A, so they aren't 3-unrepeatable.
```
3
```
```
5
```
```
1
```
```
Returns: ""
```
The only possible string is AAAAA, which is not 3-unrepeatable.
```
3
```
```
10
```
```
2
```
```
Returns: "AABAABABAA"
```

Returns: "AABAABABAABAABBAABAABABAABAABBAABAABABAABABBAABAAB"

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.