3713. Longest Balanced Substring I

Description

You are given a string s consisting of lowercase English letters.

A of s is called balanced if all distinct characters in the substring appear the same number of times.

Return the length of the longest balanced substring of s.

 

Example 1:

Input: s = "abbac"

Output: 4

Explanation:

The longest balanced substring is "abba" because both distinct characters 'a' and 'b' each appear exactly 2 times.

Example 2:

Input: s = "zzabccy"

Output: 4

Explanation:

The longest balanced substring is "zabc" because the distinct characters 'z', 'a', 'b', and 'c' each appear exactly 1 time.​​​​​​​

Example 3:

Input: s = "aba"

Output: 2

Explanation:

​​​​​​​One of the longest balanced substrings is "ab" because both distinct characters 'a' and 'b' each appear exactly 1 time. Another longest balanced substring is "ba".

 

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

 

Solutions

Solution: Hash Table

• Time complexity: O(n²)
• Space complexity: O(26 -> 1)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const longestBalanced = function (s) {
  const n = s.length;
  const BASE_CODE = 'a'.charCodeAt(0);
  let result = 0;

  const isBalance = counts => {
    let targetCount = 0;

    for (const count of counts) {
      if (!count) continue;

      if (!targetCount) {
        targetCount = count;
      }

      if (count !== targetCount) return false;
    }

    return true;
  };

  for (let a = 0; a < n; a++) {
    const counts = new Array(26).fill(0);

    for (let b = a; b < n; b++) {
      const code = s[b].charCodeAt(0) - BASE_CODE;

      counts[code] += 1;

      if (isBalance(counts)) {
        const len = b - a + 1;

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

  return result;
};