## 1643. Kth Smallest Instructions

Bob is standing at cell `(0, 0)`

, and he wants to reach `destination`

: `(row, column)`

. He can only travel **right** and **down**. You are going to help Bob by providing **instructions** for him to reach `destination`

.

The **instructions** are represented as a string, where each character is either:

`'H'`

, meaning move horizontally (go**right**), or`'V'`

, meaning move vertically (go**down**).

Multiple **instructions** will lead Bob to `destination`

. For example, if `destination`

is `(2, 3)`

, both `"HHHVV"`

and `"HVHVH"`

are valid **instructions**.

However, Bob is very picky. Bob has a lucky number `k`

, and he wants the `k`

^{th}**lexicographically smallest instructions** that will lead him to `destination`

. `k`

is **1-indexed**.

Given an integer array `destination`

and an integer `k`

, return *the *`k`

^{th}* lexicographically smallest instructions that will take Bob to *

`destination`

.

**Example 1:**

Input:destination = [2,3], k = 1Output:"HHHVV"Explanation:All the instructions that reach (2, 3) in lexicographic order are as follows: ["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"].

**Example 2:**

Input:destination = [2,3], k = 2Output:"HHVHV"

**Example 3:**

Input:destination = [2,3], k = 3Output:"HHVVH"

**Constraints:**

`destination.length == 2`

`1 <= row, column <= 15`

`1 <= k <= nCr(row + column, row)`

, where`nCr(a, b)`

denotes`a`

choose`b`

.

## Rust Solution

```
struct Solution;
impl Solution {
fn kth_smallest_path(destination: Vec<i32>, k: i32) -> String {
let n = (destination[0] + 1) as usize;
let m = (destination[1] + 1) as usize;
let mut res = "".to_string();
let mut dp = vec![vec![0; m]; n];
for i in (0..n).rev() {
for j in (0..m).rev() {
if i == n - 1 && j == m - 1 {
dp[i][j] = 1;
continue;
}
if i == n - 1 {
dp[i][j] = dp[i][j + 1];
continue;
}
if j == m - 1 {
dp[i][j] = dp[i + 1][j];
continue;
}
dp[i][j] = dp[i][j + 1] + dp[i + 1][j];
}
}
Self::build(0, 0, k, &mut res, &dp, n, m);
res
}
fn build(i: usize, j: usize, k: i32, path: &mut String, dp: &[Vec<i32>], n: usize, m: usize) {
if i == n - 1 && j == m - 1 {
return;
}
if i == n - 1 {
path.push('H');
Self::build(i, j + 1, k, path, dp, n, m);
return;
}
if j == m - 1 {
path.push('V');
Self::build(i + 1, j, k, path, dp, n, m);
return;
}
if k <= dp[i][j + 1] {
path.push('H');
Self::build(i, j + 1, k, path, dp, n, m);
} else {
path.push('V');
Self::build(i + 1, j, k - dp[i][j + 1], path, dp, n, m);
}
}
}
#[test]
fn test() {
let destination = vec![2, 3];
let k = 1;
let res = "HHHVV".to_string();
assert_eq!(Solution::kth_smallest_path(destination, k), res);
let destination = vec![2, 3];
let k = 2;
let res = "HHVHV".to_string();
assert_eq!(Solution::kth_smallest_path(destination, k), res);
let destination = vec![2, 3];
let k = 3;
let res = "HHVVH".to_string();
assert_eq!(Solution::kth_smallest_path(destination, k), res);
}
```

Having problems with this solution? Click here to submit an issue on github.