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: Dynamic Programming

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

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const largestVariance = function (s) {
  const BASE_CODE = 'a'.charCodeAt(0);
  const codes = [...s].map(char => char.charCodeAt(0) - BASE_CODE);
  let result = 0;

  const kadane = (a, b) => {
    let countA = 0;
    let countB = 0;
    let variance = 0;
    let hasPrevB = false;

    for (const code of codes) {
      if (code !== a && code !== b) continue;

      if (code === a) {
        countA += 1;
      } else {
        countB += 1;
      }

      if (countB > 0) {
        variance = Math.max(countA - countB, variance);
      } else if (hasPrevB) {
        variance = Math.max(countA - 1, variance);
      }

      if (countB > countA) {
        countA = 0;
        countB = 0;
        hasPrevB = true;
      }
    }

    return variance;
  };

  for (let a = 0; a < 26; a++) {
    for (let b = 0; b < 26; b++) {
      if (a === b) continue;

      const variance = kadane(a, b);

      result = Math.max(variance, result);
    }
  }

  return result;
};