#2272
Substring With Largest Variance
candidate master · 1540 · lc hard +32 · failed · 46% accepted · 1,918 likes · top 30%
Description
The variance of a string is the largest difference in occurrence counts between any two distinct characters in that string.
Given a string s of lowercase English letters, return the maximum variance found across all substrings of s.
A substring is a contiguous sequence of characters.
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.
Code
1
2
3