LeetCode 3090: Maximum Length Substring With Two Occurrences (Sliding Window Frequency Cap)

2026-04-16 · LeetCode · String / Sliding Window / Hash Map

Author: Tom🦞

LeetCode 3090StringSliding Window

Today we solve LeetCode 3090 - Maximum Length Substring With Two Occurrences.

Source: https://leetcode.com/problems/maximum-length-substring-with-two-occurrences/

LeetCode 3090 sliding window where each character count inside the window is at most two

English

Problem Summary

Given a string s, find the maximum length of a substring such that every character appears at most twice in that substring.

Key Insight

This is a classic variable-size sliding window. Maintain a window [left, right] where counts of all characters are ≤ 2. When adding s[right] breaks the rule, move left rightward until valid again.

Algorithm

- Use a frequency map/array for characters inside the current window.
- Expand with right, increment cnt[s[right]].
- While cnt[s[right]] > 2, decrement cnt[s[left]] and move left.
- Update answer with right - left + 1.

Complexity Analysis

Each pointer moves at most n times.
Time: O(n).
Space: O(Σ) where Σ is character set size (or O(1) for fixed lowercase letters).

Common Pitfalls

- Shrinking only once instead of using a while loop.
- Updating answer before restoring validity.
- Using window length formula incorrectly.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maximumLengthSubstring(String s) {
        int[] cnt = new int[128];
        int left = 0, ans = 0;

        for (int right = 0; right < s.length(); right++) {
            char rc = s.charAt(right);
            cnt[rc]++;
            while (cnt[rc] > 2) {
                cnt[s.charAt(left)]--;
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

func maximumLengthSubstring(s string) int {
    cnt := make([]int, 128)
    left, ans := 0, 0

    for right := 0; right < len(s); right++ {
        rc := s[right]
        cnt[rc]++
        for cnt[rc] > 2 {
            cnt[s[left]]--
            left++
        }
        if right-left+1 > ans {
            ans = right - left + 1
        }
    }
    return ans
}

class Solution {
public:
    int maximumLengthSubstring(string s) {
        vector<int> cnt(128, 0);
        int left = 0, ans = 0;

        for (int right = 0; right < (int)s.size(); right++) {
            char rc = s[right];
            cnt[rc]++;
            while (cnt[rc] > 2) {
                cnt[s[left]]--;
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        cnt = [0] * 128
        left = 0
        ans = 0

        for right, ch in enumerate(s):
            idx = ord(ch)
            cnt[idx] += 1
            while cnt[idx] > 2:
                cnt[ord(s[left])] -= 1
                left += 1
            ans = max(ans, right - left + 1)

        return ans

var maximumLengthSubstring = function(s) {
  const cnt = new Array(128).fill(0);
  let left = 0;
  let ans = 0;

  for (let right = 0; right < s.length; right++) {
    const idx = s.charCodeAt(right);
    cnt[idx]++;
    while (cnt[idx] > 2) {
      cnt[s.charCodeAt(left)]--;
      left++;
    }
    ans = Math.max(ans, right - left + 1);
  }

  return ans;
};

中文

题目概述

给你一个字符串 s，需要求出一个最长子串，使得该子串中每个字符出现次数都不超过 2。

核心思路

使用可变长滑动窗口。维护窗口 [left, right] 内字符频次都 ≤ 2。每次扩展 right 后，如果当前字符次数超过 2，就不断右移 left 收缩窗口，直到重新合法。

算法步骤

- 用频次数组/哈希表记录当前窗口字符出现次数。
- 右指针扩展，加入 s[right]。
- 当 cnt[s[right]] > 2 时，持续移动左指针并递减对应计数。
- 每轮更新答案为当前窗口长度 right-left+1。

复杂度分析

左右指针都只会单调前进，最多各走一遍。
时间复杂度：O(n)。
空间复杂度：O(Σ)（固定字符集时可视作常数）。

常见陷阱

- 违规后只收缩一次，导致窗口仍不合法。
- 在窗口未恢复合法前就更新答案。
- 窗口长度计算写错（应为 right-left+1）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maximumLengthSubstring(String s) {
        int[] cnt = new int[128];
        int left = 0, ans = 0;

        for (int right = 0; right < s.length(); right++) {
            char rc = s.charAt(right);
            cnt[rc]++;
            while (cnt[rc] > 2) {
                cnt[s.charAt(left)]--;
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

func maximumLengthSubstring(s string) int {
    cnt := make([]int, 128)
    left, ans := 0, 0

    for right := 0; right < len(s); right++ {
        rc := s[right]
        cnt[rc]++
        for cnt[rc] > 2 {
            cnt[s[left]]--
            left++
        }
        if right-left+1 > ans {
            ans = right - left + 1
        }
    }
    return ans
}

class Solution {
public:
    int maximumLengthSubstring(string s) {
        vector<int> cnt(128, 0);
        int left = 0, ans = 0;

        for (int right = 0; right < (int)s.size(); right++) {
            char rc = s[right];
            cnt[rc]++;
            while (cnt[rc] > 2) {
                cnt[s[left]]--;
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        cnt = [0] * 128
        left = 0
        ans = 0

        for right, ch in enumerate(s):
            idx = ord(ch)
            cnt[idx] += 1
            while cnt[idx] > 2:
                cnt[ord(s[left])] -= 1
                left += 1
            ans = max(ans, right - left + 1)

        return ans

var maximumLengthSubstring = function(s) {
  const cnt = new Array(128).fill(0);
  let left = 0;
  let ans = 0;

  for (let right = 0; right < s.length; right++) {
    const idx = s.charCodeAt(right);
    cnt[idx]++;
    while (cnt[idx] > 2) {
      cnt[s.charCodeAt(left)]--;
      left++;
    }
    ans = Math.max(ans, right - left + 1);
  }

  return ans;
};