title

problem link

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

let me sort out the question.

given a string s ,we need to find the greatest difference between the number of occurrences of any 2 characters among all the substrings of s.

and the string s consists of 26 lowercase english letters.

we can enumerate the character a and character b with two nested for loops, the time is o(26*26).

after that, the further question is how to get the greatest difference between a and b among all the substrings of s.

I think we can use dynamic programming technique. Plus it can be abstracted into another common problem: the largest sum of subarray.

when char a occurs, sum += 1, when char b occurs, sum -= 1, just get the largest sum. but note that what we want is if and only if when there are two chars. so there are some different.

define dp(i,0) as the largest sum value when ended with s [i] and don’t care the existence of char b.

so dp(i,0) has the following results.

if s[i] == a, dp(i,0) = dp(i-1,0)+1.

if s[i] == b, dp(i,0) = dp(i-1,0) -1.

if dp(i,0) < 0, dp(i,0) = 0.

dp(i,1) represents the largetst sum value when ended with s[i] and it contains at least 1 b.

dp(i,1) = [ dp(i-1,0)+1 if s[i] == a, dp(i,0) if s[i] == b ]

so we can get the largest sum among all the substrings of s when we know the char a and char b.

And the time complexity of this part is o(n).

So the total time complexity is O(n * 26 * 26)

class Solution:
    def largestVariance(self, s: str) -> int:
        n = len(s)
        if not s:
            return 0
        ans = 0
        for i in range(ord('a'), ord('z') + 1, 1):
            a = chr(i)
            for j in range(ord('a'), ord('z') + 1, 1):
                b = chr(j)
                # a- b
                if a == b: continue
                diff = 0
                diff_with_b = float('-inf')
                for k, c in enumerate(s):
                    if c == a:
                        diff += 1
                        diff_with_b += 1
                    elif c == b:
                        diff -= 1
                        diff_with_b = diff
                        if diff < 0:
                            diff = 0
                    if diff_with_b > 0:
                        ans = max(ans, diff_with_b)
        return ans


if __name__ == '__main__':
    f = Solution().largestVariance
    print(f(s="aababbb"))
    print(f(s="abcde"))
    enumerate