3298. Count Substrings That Can Be Rearranged to Contain a String II Hard

1/**
2 * [3298] Count Substrings That Can Be Rearranged to Contain a String II
3 *
4 * You are given two strings word1 and word2.
5 * A string x is called valid if x can be rearranged to have word2 as a <span data-keyword="string-prefix">prefix</span>.
6 * Return the total number of valid <span data-keyword="substring-nonempty">substrings</span> of word1.
7 * Note that the memory limits in this problem are smaller than usual, so you must implement a solution with a linear runtime complexity.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">word1 = "bcca", word2 = "abc"</span>
12 * Output: <span class="example-io">1</span>
13 * Explanation:
14 * The only valid substring is "bcca" which can be rearranged to "abcc" having "abc" as a prefix.
15 * </div>
16 * <strong class="example">Example 2:
17 * <div class="example-block">
18 * Input: <span class="example-io">word1 = "abcabc", word2 = "abc"</span>
19 * Output: <span class="example-io">10</span>
20 * Explanation:
21 * All the substrings except substrings of size 1 and size 2 are valid.
22 * </div>
23 * <strong class="example">Example 3:
24 * <div class="example-block">
25 * Input: <span class="example-io">word1 = "abcabc", word2 = "aaabc"</span>
26 * Output: <span class="example-io">0</span>
27 * </div>
28 *  
29 * Constraints:
30 * 
31 * 	1 <= word1.length <= 10^6
32 * 	1 <= word2.length <= 10^4
33 * 	word1 and word2 consist only of lowercase English letters.
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii/
39// discuss: https://leetcode.com/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn valid_substring_count(word1: String, word2: String) -> i64 {
45        
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_3298() {
57    }
58}
59