SP10608 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. Let’s say we sort the unique strings – **first by length and then lexicographically**. The N $ ^{th} $ 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

A single line: the N $ ^{th} $ unique string in the sorted list.