30. Substring with Concatenation of All Words Hard

1/**
2 * [30] Substring with Concatenation of All Words
3 *
4 * You are given a string s and an array of strings words. All the strings of words are of the same length.
5 * A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.
6 * 
7 * 	For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words.
8 * 
9 * Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.
10 *  
11 * Example 1:
12 * 
13 * Input: s = "barfoothefoobarman", words = ["foo","bar"]
14 * Output: [0,9]
15 * Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6.
16 * The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
17 * The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
18 * The output order does not matter. Returning [9,0] is fine too.
19 * 
20 * Example 2:
21 * 
22 * Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
23 * Output: []
24 * Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16.
25 * There is no substring of length 16 is s that is equal to the concatenation of any permutation of words.
26 * We return an empty array.
27 * 
28 * Example 3:
29 * 
30 * Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
31 * Output: [6,9,12]
32 * Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9.
33 * The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words.
34 * The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words.
35 * The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words.
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	1 <= s.length <= 10^4
41 * 	1 <= words.length <= 5000
42 * 	1 <= words[i].length <= 30
43 * 	s and words[i] consist of lowercase English letters.
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/substring-with-concatenation-of-all-words/
49// discuss: https://leetcode.com/problems/substring-with-concatenation-of-all-words/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
55        vec![]
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_30() {
67    }
68}
69