NextHomogeneousStrings

SRM 467 · 2009-11-12 · by vexorian

SRM 467 · 2009-11-12 · by vexorian · Dynamic Programming

Show categories

Class Name: NextHomogeneousStrings

Return Type: String

Method Name: getNext

Arg Types: (int, int, string, long long)

Problem Statement

A string is homogeneous if every contiguous substring of length n contains at most d different characters. For a String seed and a long k, the k-th homogeneous string is defined as the k-th element (0-indexed) in the list of all homogeneous strings which have the same length as seed and are lexicographically greater than or equal to seed. Only strings containing all lowercase letters ('a'-'z') should be considered. Return the k-th homogeneous string. If there are less than k+1 strings in this list, return "" instead (quotes for clarity).

Notes

If A and B are two Strings of the same length, then A comes earlier lexicographically than B if it contains a smaller character at the first position where the Strings differ.

Constraints

n will be between 1 and 9, inclusive.
d will be between 1 and n, inclusive.
k will be between 0 and 1000000000000000000 (10^18), inclusive.
seed will contain between 1 and 50 characters, inclusive.
seed will contain at least n characters.
seed will contain only lowercase letters ('a'-'z').

Examples

1
2
"aaa"
3
Returns: "ddd"

The condition n=2 and d=1 requires no two consecutive characters to be different. The only homogeneous strings in this case would be: "aaa", "bbb", "ccc", "ddd", ... , "zzz". "ddd" is the fourth one.

2
3
"abc"
0
Returns: "aca"

2
4
"ttrrzz"
6
Returns: "ttsssc"

9
9
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
1000000000000000000
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaakmluxinkecojo"

8
9
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
1000000000000000000
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaauialgggesdxfk"

2
7
"abcdefg"
0
Returns: "acaaaaa"

No longer a tricky case.

70)

2
5
"zzzzzaa"
100
Returns: ""

In this case, there are 25 homogeneous strings that follow the pattern "zzzzzXX", where X is any letter different from 'z'. There are another 25 homogeneous strings that follow the pattern "zzzzzXz". Finally, there are 26 homogeneous strings that begin with "zzzzzz". In total, there are only 25+25+26 = 76 homogeneous strings that are lexicographically greater than or equal to "zzzzzaa".

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

Coding Area

Language: C++17 · define a public class NextHomogeneousStrings with a public method string getNext(int d, int n, string seed, long long k) · 71 test cases · 2 s / 256 MB per case