TopCoder problem "UnrepeatableWords" used in SRM 323 (Division II Level Three)



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

0)
    
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.
1)
    
3
5
1
Returns: ""
The only possible string is AAAAA, which is not 3-unrepeatable.
2)
    
3
10
2
Returns: "AABAABABAA"
3)
    
3
50
2
Returns: "AABAABABAABAABBAABAABABAABAABBAABAABABAABABBAABAAB"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6603

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10003&pm=6603

Writer:

Pawa

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Problem categories:

Brute Force, Search