2272. Substring With Largest Variance

Problem Link

Description

---

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.

Solution

---

Python3

class Solution:
    def largestVariance(self, s: str) -> int:
        res = 0
        
        for a, b in permutations(set(s), 2):
            cnt = 0
            hasB = firstB = False
            
            for x in s:
                if x == a:
                    cnt += 1
                elif x == b:
                    hasB = True
                    
                    if firstB and cnt >= 0:
                        firstB = False
                    else:
                        cnt -= 1
                        
                        if cnt < 0:
                            firstB = True
                            cnt = -1
                    
                if hasB and cnt > res:
                    res = cnt
        
        return res