## 1055. Shortest Way to Form String

From any string, we can form a subsequence of that string by deleting some number of characters (possibly no deletions).

Given two strings `source` and `target`, return the minimum number of subsequences of `source` such that their concatenation equals `target`. If the task is impossible, return `-1`.

Example 1:

```Input: source = "abc", target = "abcbc"
Output: 2
Explanation: The target "abcbc" can be formed by "abc" and "bc", which are subsequences of source "abc".
```

Example 2:

```Input: source = "abc", target = "acdbc"
Output: -1
Explanation: The target string cannot be constructed from the subsequences of source string due to the character "d" in target string.
```

Example 3:

```Input: source = "xyz", target = "xzyxz"
Output: 3
Explanation: The target string can be constructed as follows "xz" + "y" + "xz".
```

Constraints:

• Both the `source` and `target` strings consist of only lowercase English letters from "a"-"z".
• The lengths of `source` and `target` string are between `1` and `1000`.

## Rust Solution

``````struct Solution;
use std::collections::HashMap;

impl Solution {
fn shortest_way(source: String, target: String) -> i32 {
let mut pos: HashMap<char, Vec<usize>> = HashMap::new();
let mut res = 1;
for (i, c) in source.char_indices() {
pos.entry(c).or_default().push(i);
}
let mut start = 0;
for c in target.chars() {
if let Some(indexes) = pos.get(&c) {
loop {
let index = Self::next(start, &indexes);
if index == 0 {
start = 0;
res += 1;
} else {
start = index;
break;
}
}
} else {
return -1;
}
}
res
}

fn next(start: usize, indexes: &[usize]) -> usize {
match indexes.binary_search(&start) {
Ok(i) => indexes[i] + 1,
Err(i) => {
if i == indexes.len() {
0
} else {
indexes[i] + 1
}
}
}
}
}

#[test]
fn test() {
let source = "abc".to_string();
let target = "abcbc".to_string();
let res = 2;
assert_eq!(Solution::shortest_way(source, target), res);
let source = "abc".to_string();
let target = "acdbc".to_string();
let res = -1;
assert_eq!(Solution::shortest_way(source, target), res);
let source = "xyz".to_string();
let target = "xzyxz".to_string();
let res = 3;
assert_eq!(Solution::shortest_way(source, target), res);
let source = "aaaaa".to_string();
let target = "aaaaaaaaaaaaa".to_string();
let res = 3;
assert_eq!(Solution::shortest_way(source, target), res);
let source = "adbsc".to_string();
let target = "addddddddddddsbc".to_string();
let res = 13;
assert_eq!(Solution::shortest_way(source, target), res);
}
``````

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