##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2272.html

# 2272. Substring With Largest Variance

• Difficulty: Hard.
• Related Topics: Array, Dynamic Programming.
• Similar Questions: Maximum Subarray.

## Problem

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

• class Solution {
public int largestVariance(String s) {
int[] freq = new int[26];
for (int i = 0; i < s.length(); i++) {
freq[s.charAt(i) - 'a']++;
}
int maxVariance = 0;
for (int a = 0; a < 26; a++) {
for (int b = 0; b < 26; b++) {
int remainingA = freq[a];
int remainingB = freq[b];
if (a == b || remainingA == 0 || remainingB == 0) {
continue;
}
int currBFreq = 0;
int currAFreq = 0;
for (int i = 0; i < s.length(); i++) {
int c = s.charAt(i) - 'a';
if (c == b) {
currBFreq++;
}
if (c == a) {
currAFreq++;
remainingA--;
}

if (currAFreq > 0) {
maxVariance = Math.max(maxVariance, currBFreq - currAFreq);
}
if (currBFreq < currAFreq && remainingA >= 1) {
currBFreq = 0;
currAFreq = 0;
}
}
}
}
return maxVariance;
}
}

############

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;
}
}

• 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

############

# 2272. Substring With Largest Variance
# https://leetcode.com/problems/substring-with-largest-variance

class Solution:
def largestVariance(self, s: str) -> int:
n = len(s)
res = 0

for a, b in permutations(set(s), 2):
cnt = 0
hasB = firstB = False

for x in s:
if x == a:
cnt += 1

if 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


• 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;
}
};

• 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
}

func max(a, b int) int {
if a > b {
return a
}
return b
}


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).