76. Minimum Window Substring Hard

1/**
2 * [76] Minimum Window Substring
3 *
4 * Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
5 * The testcases will be generated such that the answer is unique.
6 * A substring is a contiguous sequence of characters within the string.
7 *  
8 * Example 1:
9 *
10 * Input: s = "ADOBECODEBANC", t = "ABC"
11 * Output: "BANC"
12 * Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
13 *
14 * Example 2:
15 *
16 * Input: s = "a", t = "a"
17 * Output: "a"
18 * Explanation: The entire string s is the minimum window.
19 *
20 * Example 3:
21 *
22 * Input: s = "a", t = "aa"
23 * Output: ""
24 * Explanation: Both 'a's from t must be included in the window.
25 * Since the largest window of s only has one 'a', return empty string.
26 *
27 *  
28 * Constraints:
29 *
30 * m == s.length
31 * n == t.length
32 * 1 <= m, n <= 10^5
33 * s and t consist of uppercase and lowercase English letters.
34 *
35 *  
36 * Follow up: Could you find an algorithm that runs in O(m + n) time?
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/minimum-window-substring/
41// discuss: https://leetcode.com/problems/minimum-window-substring/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44use std::collections::HashMap;
45
46impl Solution {
47    pub fn min_window(s: String, t: String) -> String {
48        let mut map: HashMap<char, i32> = HashMap::new();
49        t.chars().for_each(|c| {
50            map.entry(c).and_modify(|v| *v += 1).or_insert(1);
51        });
52        let mut has = map.len();
53
54        let chs: Vec<char> = s.chars().collect();
55        let (mut start, mut end, mut min, mut min_start, mut min_end) = (0, 0, i32::MAX, 0, 0);
56
57        while end < chs.len() {
58            map.entry(chs[end]).and_modify(|v| {
59                *v -= 1;
60                if *v == 0 {
61                    has -= 1;
62                }
63            });
64
65            if has > 0 {
66                end += 1;
67            } else {
68                while has == 0 {
69                    if end - start + 1 < min as usize {
70                        min = (end - start + 1) as i32;
71                        min_end = end;
72                        min_start = start;
73                    }
74
75                    map.entry(chs[start]).and_modify(|v| {
76                        *v += 1;
77                        if *v == 1 {
78                            has += 1;
79                        }
80                    });
81                    start += 1;
82                }
83                end += 1;
84            }
85        }
86
87        if min == i32::MAX {
88            return String::new()
89        }
90        {
91            s[min_start..min_end + 1].to_string()
92        }
93    }
94}
95
96// submission codes end
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101
102    #[test]
103    fn test_76() {
104        assert_eq!(
105            Solution::min_window("ADOBECODEBANC".to_owned(), "ABC".to_owned()),
106            "BANC".to_owned()
107        );
108        assert_eq!(
109            Solution::min_window("a".to_owned(), "aa".to_owned()),
110            "".to_owned()
111        );
112    }
113}
114