30. Substring with Concatenation of All Words

You are given a string `s` and an array of strings `words` of the same length. Return all starting indices of substring(s) in `s` that is a concatenation of each word in `words` exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Example 1:

```Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
```

Example 2:

```Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
```

Example 3:

```Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
```

Constraints:

• `1 <= s.length <= 104`
• `s` consists of lower-case English letters.
• `1 <= words.length <= 5000`
• `1 <= words[i].length <= 30`
• `words[i]` consists of lower-case English letters.

30. Substring with Concatenation of All Words
``````struct Solution;

use std::collections::HashMap;

impl Solution {
fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
let n = s.len();
if n == 0 {
return vec![];
}
let mut count: HashMap<&str, usize> = HashMap::new();
let m = words.len();
if m == 0 {
return vec![];
}
let size = words.len();
if m * size > n {
return vec![];
}
for w in &words {
*count.entry(w).or_default() += 1;
}
let mut res = vec![];
'outer: for i in 0..=n - m * size {
let mut cur: HashMap<&str, usize> = HashMap::new();
for j in 0..m {
let w = &s[i + j * size..i + (j + 1) * size];
if let Some(x) = count.get(w) {
let y = cur.entry(w).or_default();
*y += 1;
if *y > *x {
continue 'outer;
}
} else {
continue 'outer;
}
}
res.push(i as i32);
}
res
}
}

#[test]
fn test() {
let s = "barfoothefoobarman".to_string();
let words = vec_string!["foo", "bar"];
let res = vec![0, 9];
assert_eq!(Solution::find_substring(s, words), res);
let s = "wordgoodgoodgoodbestword".to_string();
let words = vec_string!["word", "good", "best", "word"];
let res: Vec<i32> = vec![];
assert_eq!(Solution::find_substring(s, words), res);
let s = "wordgoodgoodgoodbestword".to_string();
let words = vec_string!["word", "good", "best", "good"];
let res = vec!;
assert_eq!(Solution::find_substring(s, words), res);
}
``````