LeetCode 2272. Substring With Largest Variance Solution in Java, C++, Python & More | Explanation + Code

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.

Solutions

Solution 1: Enumeration + Dynamic Programming

Since the character set only contains lowercase letters, we can consider enumerating the most frequent character a and the least frequent character b. For a substring, the difference in the number of occurrences of these two characters is the variance of the substring.

Specifically, we use a double loop to enumerate a and b. We use f[0] to record the number of consecutive occurrences of character a ending at the current character, and f[1] to record the variance of the substring ending at the current character and containing both a and b. We iterate to find the maximum value of f[1].

The recurrence formula is as follows:

1. If the current character is a, then both f[0] and f[1] are incremented by 1;
2. If the current character is b, then f[1] = max(f[1] - 1, f[0] - 1), and f[0] = 0;
3. Otherwise, no need to consider.

Note that initially setting f[1] to a negative maximum value ensures that updating the answer is valid.

The time complexity is O(n × |Σ|^2), where n is the length of the string, and |Σ| is the size of the character set. The space complexity is O(1).

PythonJavaC++GoTypeScript

class Solution: def largestVariance(self, s: str) -> int: ans = 0 for a, b in permutations(ascii_lowercase, 2): if a == b: continue f = [0, -inf] for c in s: if c == a: f[0], f[1] = f[0] + 1, f[1] + 1 elif c == b: f[1] = max(f[1] - 1, f[0] - 1) f[0] = 0 if ans < f[1]: ans = f[1] return ans(code-box)

class Solution { public int largestVariance(String s) { int n = s.length(); int ans = 0; for (char a = 'a'; a <= 'z'; ++a) { for (char b = 'a'; b <= 'z'; ++b) { if (a == b) { continue; } int[] f = new int[] {0, -n}; for (int i = 0; i < n; ++i) { if (s.charAt(i) == a) { f[0]++; f[1]++; } else if (s.charAt(i) == b) { f[1] = Math.max(f[0] - 1, f[1] - 1); f[0] = 0; } ans = Math.max(ans, f[1]); } } } return ans; } }(code-box)

class Solution { public: int largestVariance(string s) { int n = s.size(); int ans = 0; for (char a = 'a'; a <= 'z'; ++a) { for (char b = 'a'; b <= 'z'; ++b) { if (a == b) { continue; } int f[2] = {0, -n}; for (char c : s) { if (c == a) { f[0]++; f[1]++; } else if (c == b) { f[1] = max(f[1] - 1, f[0] - 1); f[0] = 0; } ans = max(ans, f[1]); } } } return ans; } };(code-box)

func largestVariance(s string) int { ans, n := 0, len(s) for a := 'a'; a <= 'z'; a++ { for b := 'a'; b <= 'z'; b++ { if a == b { continue } f := [2]int{0, -n} for _, c := range s { if c == a { f[0]++ f[1]++ } else if c == b { f[1] = max(f[1]-1, f[0]-1) f[0] = 0 } ans = max(ans, f[1]) } } } return ans }(code-box)

function largestVariance(s: string): number { const n: number = s.length; let ans: number = 0; for (let a = 97; a <= 122; ++a) { for (let b = 97; b <= 122; ++b) { if (a === b) { continue; } const f: number[] = [0, -n]; for (let i = 0; i < n; ++i) { if (s.charCodeAt(i) === a) { f[0]++; f[1]++; } else if (s.charCodeAt(i) === b) { f[1] = Math.max(f[0] - 1, f[1] - 1); f[0] = 0; } ans = Math.max(ans, f[1]); } } } return ans; }(code-box)