3090. Maximum Length Substring With Two Occurrences

Description

Given a string s, return the maximum length of a  such that it contains at most two occurrences of each character.

 

Example 1:

Input: s = "bcbbbcba"

Output: 4

Explanation:

The following substring has a length of 4 and contains at most two occurrences of each character: "bcbbbcba".

Example 2:

Input: s = "aaaa"

Output: 2

Explanation:

The following substring has a length of 2 and contains at most two occurrences of each character: "aaaa".

 

Constraints:

• 2 <= s.length <= 100
• s consists only of lowercase English letters.

 

Solutions

Solution: Sliding Window

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

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const maximumLengthSubstring = function (s) {
  const n = s.length;
  const countMap = new Map();
  let left = 0;
  let result = 0;

  for (let index = 0; index < n; index++) {
    const char = s[index];
    const count = countMap.get(char) ?? 0;

    countMap.set(char, count + 1);

    while (countMap.get(char) > 2) {
      const leftChar = s[left];
      const leftCount = countMap.get(leftChar);

      if (leftCount === 1) {
        countMap.delete(leftChar);
      } else {
        countMap.set(leftChar, leftCount - 1);
      }

      left += 1;
    }

    const len = index - left + 1;

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

  return result;
};