K-th Route in Alphabetical Order

Hard

A warehouse robot stands in cell (0, 0) and must reach cell target = [row, col]. It can only move right or down. A route is written as a string of 'H' (one step right, column + 1) and 'V' (one step down, row + 1). For instance, [1, 2] is reached by "HHV", "HVH" and "VHH". Sort all routes to target alphabetically ('H' < 'V'). Return the route in position k (counting from 1).

Example 1

target=[1, 2], k=2 → 'HVH'

There are three routes, "HHV", "HVH" and "VHH"; the second in alphabetical order is "HVH".

Example 2

target=[2, 2], k=6 → 'VVHH'

Of the six routes, the last alphabetically goes down twice first: "VVHH".

Example 3

target=[3, 1], k=1 → 'HVVV'

Constraints

len(target) == 2
1 ≤ row, col ≤ 15
1 ≤ k ≤ C(row + col, row), the total number of routes

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Dynamic Programming Combinatorics

Similar problems

A Fair Split of Colored Beads Hard Other Orders for the Same Search Tree Hard Split Into a Climb and a Descent Hard Split Into a Climb and a Descent: Large Values Hard Picks Without a Fixed Gap Medium

Input

target=[1, 2], k=2

Expected

'HVH'

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