Skip to content

3090. Maximum Length Substring With Two Occurrences

Description

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.

Solutions

Solution 1: Two Pointers

We use two pointers \(i\) and \(j\) to maintain a sliding window, and an array \(cnt\) to record the occurrence times of each character in the window.

In each iteration, we add the character \(c\) at the pointer \(j\) into the window, then check if \(cnt[c]\) is greater than \(2\). If it is, we move the pointer \(i\) to the right until \(cnt[c]\) is less than or equal to \(2\). At this point, we update the answer \(ans = \max(ans, j - i + 1)\).

Finally, we return the answer \(ans\).

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(|\Sigma|)\), where \(\Sigma\) is the character set, and in this problem, \(\Sigma = 26\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        cnt = Counter()
        ans = i = 0
        for j, c in enumerate(s):
            cnt[c] += 1
            while cnt[c] > 2:
                cnt[s[i]] -= 1
                i += 1
            ans = max(ans, j - i + 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int maximumLengthSubstring(String s) {
        int[] cnt = new int[26];
        int ans = 0;
        for (int i = 0, j = 0; j < s.length(); ++j) {
            int idx = s.charAt(j) - 'a';
            ++cnt[idx];
            while (cnt[idx] > 2) {
                --cnt[s.charAt(i++) - 'a'];
            }
            ans = Math.max(ans, j - i + 1);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int maximumLengthSubstring(string s) {
        int cnt[26]{};
        int ans = 0;
        for (int i = 0, j = 0; j < s.length(); ++j) {
            int idx = s[j] - 'a';
            ++cnt[idx];
            while (cnt[idx] > 2) {
                --cnt[s[i++] - 'a'];
            }
            ans = max(ans, j - i + 1);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func maximumLengthSubstring(s string) (ans int) {
    cnt := [26]int{}
    i := 0
    for j, c := range s {
        idx := c - 'a'
        cnt[idx]++
        for cnt[idx] > 2 {
            cnt[s[i]-'a']--
            i++
        }
        ans = max(ans, j-i+1)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function maximumLengthSubstring(s: string): number {
    let ans = 0;
    const cnt: number[] = Array(26).fill(0);
    for (let i = 0, j = 0; j < s.length; ++j) {
        const idx = s[j].charCodeAt(0) - 'a'.charCodeAt(0);
        ++cnt[idx];
        while (cnt[idx] > 2) {
            --cnt[s[i++].charCodeAt(0) - 'a'.charCodeAt(0)];
        }
        ans = Math.max(ans, j - i + 1);
    }
    return ans;
}

Comments