2272. Substring With Largest Variance
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 <= 104sconsists 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:
If the current character is $a$, then both $f[0]$ and $f[1]$ are incremented by $1$;
If the current character is $b$, then $f[1] = \max(f[1] - 1, f[0] - 1)$, and $f[0] = 0$;
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 \times |\Sigma|^2)$, where $n$ is the length of the string, and $|\Sigma|$ is the size of the character set. The space complexity is $O(1)$.
Python3
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
Java
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;
}
}
C++
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;
}
};
Go
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
}
TypeScript
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;
}