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 <= 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 \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)\).

Python3JavaC++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

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

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

Comments