UnrepeatableWords

SRM 323 · 2006-10-19 · by Pawa

SRM 323 · 2006-10-19 · by Pawa · Brute Force, Search

Show categories

Class Name: UnrepeatableWords

Return Type: String

Method Name: getWord

Arg Types: (int, int, int)

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.

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"

3
50
2
Returns: "AABAABABAABAABBAABAABABAABAABBAABAABABAABABBAABAAB"

4
50
3
Returns: "AAABAAABAAABAAACAAABAAABAAABAAACAAABAAABAAABAAACAA"

Submissions are judged against all 31 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class UnrepeatableWords with a public method string getWord(int k, int n, int allowed) · 31 test cases · 2 s / 256 MB per case