[LeetCode] 3090. Maximum Length Substring With Two Occurrences

Given a string s, return the maximum length of a substring 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.

每个字符最多出现两次的最长子字符串。

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的 最大 长度。

思路

这道题不难看出是用滑动窗口的思路，而且这道题很像159题。这道题左指针的移动条件是只要某个字母的出现次数大于2，就移动左指针。其余思路同一般滑动窗口题。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int maximumLengthSubstring(String s) {
        int start = 0;
        int end = 0;
        int[] map = new int[256];
        int res = 0;
        while (end < s.length()) {
            char c1 = s.charAt(end);
            end++;
            map[c1]++;
            // 如果某个字母的出现次数大于2，就移动左指针
            while (map[c1] > 2) {
                char c2 = s.charAt(start);
                start++;
                map[c2]--;
            }
            res = Math.max(res, end - start);
        }
        return res;
    }
}