Question

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

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
}