2272 Substring With Largest Variance

🔀 Pick One

The variance of a string is defined as the largest difference between the number of occurrences of any 2 characters present in the string. Note the two characters may or may not be the same.

Given a string s consisting of lowercase English letters only, return the largest variance possible among all substrings of s.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "aababbb"
Output: 3
Explanation:
All possible variances along with their respective substrings are listed below:
- Variance 0 for substrings "a", "aa", "ab", "abab", "aababb", "ba", "b", "bb", and "bbb".
- Variance 1 for substrings "aab", "aba", "abb", "aabab", "ababb", "aababbb", and "bab".
- Variance 2 for substrings "aaba", "ababbb", "abbb", and "babb".
- Variance 3 for substring "babbb".
Since the largest possible variance is 3, we return it.

Example 2:

Input: s = "abcde"
Output: 0
Explanation:
No letter occurs more than once in s, so the variance of every substring is 0.

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters.
 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

class Solution:
    def largestVariance(self, s: str) -> int:
        chars = set(s)
        ans = 0
        for a in chars:
            for b in chars:
                diff = 0
                # max and min of diff
				# result should be max(diff - min_diff, max_diff - diff)
				# e.g. "baabaa"
                #      at index = 0, min_diff = -1
                #      when index = 5, diff = 4 - 2 = 2
                #      result = diff - min_diff = 2 - (-1) = 3
                max_diff = min_diff = 0
                last_a_diff = last_b_diff = 0
                meet_a = meet_b = False
                for c in s:
                    if c == a:
                        meet_a = True
                        diff += 1
                        max_diff = max(last_a_diff, max_diff)
                        last_a_diff = diff
                    elif c == b:
                        meet_b = True
                        diff -= 1
                        min_diff = min(last_b_diff, min_diff)
                        last_b_diff = diff
                    else:
                        continue
                    if meet_a and meet_b:
                        ans = max(
                            diff - min_diff,
                            max_diff - diff,
                            ans,
                        )
        return ans