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

Thinking

Every character in the substring may appear at most twice. \(n \le 100\) would allow enumeration, but the constraint is a classic sliding window.

After the right end absorbs a character, if some count exceeds \(2\) the left end must advance until that count is back to \(2\). A valid window updates the maximum length.

A hash of counts plus two pointers does this in one pass.

We use two pointers \(l\) and \(r\) 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 \(r\) into the window, then check if \(cnt[c]\) is greater than \(2\). If it is, we move the pointer \(l\) to the right until \(cnt[c]\) is less than or equal to \(2\). At this point, we update the answer \(ans = \max(ans, r - l + 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:
        ans = l = 0
        cnt = defaultdict(int)
        for r, c in enumerate(s):
            cnt[c] += 1
            while cnt[c] > 2:
                cnt[s[l]] -= 1
                l += 1
            ans = max(ans, r - l + 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 ans = 0;
        int[] cnt = new int[26];
        for (int l = 0, r = 0; r < s.length(); ++r) {
            int idx = s.charAt(r) - 'a';
            ++cnt[idx];
            while (cnt[idx] > 2) {
                --cnt[s.charAt(l++) - 'a'];
            }
            ans = Math.max(ans, r - l + 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 ans = 0;
        int cnt[26]{};
        for (int l = 0, r = 0; r < s.size(); ++r) {
            int idx = s[r] - 'a';
            ++cnt[idx];
            while (cnt[idx] > 2) {
                --cnt[s[l++] - 'a'];
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func maximumLengthSubstring(s string) (ans int) {
    l := 0
    cnt := [26]int{}
    for r, c := range s {
        idx := int(c - 'a')
        cnt[idx]++
        for cnt[idx] > 2 {
            cnt[s[l]-'a']--
            l++
        }
        ans = max(ans, r-l+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 l = 0, r = 0; r < s.length; ++r) {
        const idx = s[r].charCodeAt(0) - 97;
        ++cnt[idx];
        while (cnt[idx] > 2) {
            --cnt[s[l++].charCodeAt(0) - 97];
        }
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
impl Solution {
    pub fn maximum_length_substring(s: String) -> i32 {
        let mut cnt = [0; 26];
        let mut ans = 0;
        let mut l = 0;
        let s = s.as_bytes();

        for (r, &c) in s.iter().enumerate() {
            let i = (c - b'a') as usize;
            cnt[i] += 1;

            while cnt[i] > 2 {
                cnt[(s[l] - b'a') as usize] -= 1;
                l += 1;
            }

            ans = ans.max((r - l + 1) as i32);
        }

        ans
    }
}

Comments