UNICA - Unique Strings
Some people who love strings have decided to call a special group of strings as the “unique strings.”
Let’s define a(S) as the number of characters “a” the string S contains, and b(S) as the number of characters “b” the string S contains.
S is a unique string if:
1) S only contains the characters “a” and “b”
2) For every substring S’of S, | a(S’) – b(S’) | <= 3
For example, “abbab” is a unique string. However, “abbbba” is not because it includes the substring “bbbb” for which | a(“bbbb”) – b(“bbbbb”) | = 4 > 3.
Let’s say we sort the unique strings – first by length and then lexicographically. The Nth unique string is the string that appears in the position N in the sorted list. The first unique string is assigned the number 1.
The first 12 unique strings in the sorted list are: a, b, aa, ab,ba, bb, aaa, aab, aba, abb, baa, bab
A single number N (1 <= N <= 1014). Your task is to find the Nth unique string in the sorted list.
A single line: the Nth unique string in the sorted list.
Input: 10 Output: abb
Last edit: 2016-10-18 03:27:57
IO from AC solution: