A, B, C String With No Repeats

Medium

Consider strings made of the letters a, b and c in which no two neighbouring letters are equal. For example, acb, b and cacbab qualify, while bb and abcc do not. List all such strings of length length in alphabetical order and number them starting from one. Return the string with number rank. If there are fewer than rank strings, return an empty string.

Example 1

length=2, rank=4 → 'bc'

The strings of length 2 in alphabetical order are ab, ac, ba, bc, ca, cb. The fourth one is bc.

Example 2

length=4, rank=7 → 'acba'

The strings starting with a are abab, abac, abca, abcb, acab, acac, acba, acbc; the seventh is acba.

Example 3

length=3, rank=13 → ''

There are only 3 · 2 · 2 = 12 such strings of length 3, so there is no thirteenth.

Constraints

1 ≤ length ≤ 10
1 ≤ rank ≤ 2000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Backtracking

Similar problems

Keypad Words Medium All Balanced Bracket Strings Medium Word Traced on a Letter Grid Medium IP Addresses From a Digit String Medium Cutting a Word Into Palindromes Medium

Input

length=2, rank=4

Expected

'bc'

Run checks the first 3 tests in your browser. Submit checks all 79 tests on the server, hidden ones included.