aboutsummaryrefslogtreecommitdiff
path: root/min_window_substring.rs
blob: f23402b8b4e0d2f08189ceeb21176cd38b3f180e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct Solution;

impl Solution {
    pub fn min_window(s: String, t: String) -> String {
        let mut state = [0 as isize; (b'z' - b'A' + 1) as usize];
        let mut target = [0 as isize; (b'z' - b'A' + 1) as usize];
        for b in t.bytes() {
            target[(b - b'A') as usize] += 1;
        }
        let (target, string, mut best_from, mut best_to, mut from, mut to, mut chars_found, chars_expected) =
            (target, s.as_bytes(), 0, 0, 0, 0, 0, target.iter().filter(|&&ch| ch > 0).count());
        while to < string.len() {
            let ch = (string[to] - b'A') as usize;
            if target[ch] > 0 {
                if state[ch] + 1 == target[ch] {
                    chars_found += 1;
                }
                state[ch] += 1;
            }
            if chars_found == chars_expected {
                let mut fch = (string[from] - b'A') as usize;
                while target[fch] == 0 || state[fch] > target[fch] {
                    if state[fch] > 0 {
                        state[fch] -= 1;
                    }
                    from += 1;
                    fch = (string[from] - b'A') as usize;
                }
                if to - from < best_to - best_from || best_to == 0 {
                    best_from = from;
                    best_to = to + 1;
                }
            }
            to += 1;
        }
        s[best_from..best_to].to_string()
    }
}

fn main() {
    let (s, t) = (String::from("ADOBECODEBANC"), String::from("ABC"));
    print!("{}", Solution::min_window(s, t));
}