2272. Substring With Largest Variance Hard

1use std::collections::HashMap;
2
3/**
4 * [2272] Substring With Largest Variance
5 *
6 * The variance of a string is defined as the largest difference between the number of 
7 * occurrences of any 2 characters present in the string. Note the two characters may
8 * or may not be the same.
9 * Given a string s consisting of lowercase English letters only, return the largest
10 * variance possible among all substrings of s.
11 * A substring is a contiguous sequence of characters within a string.
12 *  
13 * Example 1:
14 * 
15 * Input: s = "aababbb"
16 * Output: 3
17 * Explanation:
18 * All possible variances along with their respective substrings are listed below:
19 * - Variance 0 for substrings "a", "aa", "ab", "abab", "aababb", "ba", "b", "bb", and "bbb".
20 * - Variance 1 for substrings "aab", "aba", "abb", "aabab", "ababb", "aababbb", and "bab".
21 * - Variance 2 for substrings "aaba", "ababbb", "abbb", and "babb".
22 * - Variance 3 for substring "babbb".
23 * Since the largest possible variance is 3, we return it.
24 * 
25 * Example 2:
26 * 
27 * Input: s = "abcde"
28 * Output: 0
29 * Explanation:
30 * No letter occurs more than once in s, so the variance of every substring is 0.
31 * 
32 *  
33 * Constraints:
34 * 
35 * 1 <= s.length <= 10^4
36 * s consists of lowercase English letters.
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/substring-with-largest-variance/
42// discuss: https://leetcode.com/problems/substring-with-largest-variance/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn largest_variance(s: String) -> i32 {
48        let mut max = 0;
49        let mut map: HashMap<char, i32> = HashMap::new();
50        for c in s.chars() {
51            match map.get(&c).cloned() {
52                Some(x) => map.insert(c, x + 1),
53                None => map.insert(c, 1)
54            };
55        }
56        for a in map.keys() {
57            for b in map.keys() {
58                let mut current: i32 = 0;
59                let mut legit = false;
60                let mut start_with_b = false;
61                for c in s.chars() {
62                    if c == *a {
63                        current += 1;
64                    }
65
66                    if c == *b {
67                        legit = true;
68                        if start_with_b && current >= 0 {
69                            start_with_b = false;
70                        } else {
71                            current -= 1;
72                            if current < 0 {
73                                start_with_b = true;
74                                current = -1;
75                            }
76                        }
77                    }
78
79                    if legit && current > max {
80                        max = current;
81                    }
82                }
83            }
84        }
85        max
86    }
87}
88
89// submission codes end
90
91#[cfg(test)]
92mod tests {
93    use super::*;
94
95    #[test]
96    fn test_2272() {
97        assert_eq!(Solution::largest_variance("aababbb".to_string()), 3);
98        assert_eq!(Solution::largest_variance("abbaaabzaabaaaaaaaaaaaaa".to_string()), 18);
99    }
100}
101