Problem

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

Examples

Example 1

1
2
3
4
5
6
7
8
9


Input: s = "bcbbbcba"

Output: 4

Explanation:

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

Example 2

1
2
3
4
5
6
7
8
9


Input: s = "aaaa"

Output: 2

Explanation:

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

Constraints

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

Solution

Method 1 – Sliding Window with Hash Map

Intuition

We want the longest substring where each character appears at most twice. We can use a sliding window and a hash map to count occurrences. When a character appears more than twice, move the left pointer to shrink the window until all counts are at most two.

Approach

  1. Initialize a hash map to count character occurrences, left pointer l = 0, and ans = 0.
  2. Iterate with right pointer r over the string:
    • Increment the count for s[r].
    • While any character’s count > 2, decrement s[l] and move l right.
    • Update ans with the current window size.
  3. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int maxLengthSubstring(string s) {
        unordered_map<char, int> cnt;
        int l = 0, ans = 0;
        for (int r = 0; r < s.size(); ++r) {
            cnt[s[r]]++;
            while (cnt[s[r]] > 2) {
                cnt[s[l]]--;
                l++;
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func maxLengthSubstring(s string) int {
    cnt := map[byte]int{}
    l, ans := 0, 0
    for r := 0; r < len(s); r++ {
        cnt[s[r]]++
        for cnt[s[r]] > 2 {
            cnt[s[l]]--
            l++
        }
        if r-l+1 > ans {
            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 maxLengthSubstring(String s) {
        Map<Character, Integer> cnt = new HashMap<>();
        int l = 0, ans = 0;
        for (int r = 0; r < s.length(); ++r) {
            cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
            while (cnt.get(s.charAt(r)) > 2) {
                cnt.put(s.charAt(l), cnt.get(s.charAt(l)) - 1);
                l++;
            }
            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 {
    fun maxLengthSubstring(s: String): Int {
        val cnt = mutableMapOf<Char, Int>()
        var l = 0
        var ans = 0
        for (r in s.indices) {
            cnt[s[r]] = cnt.getOrDefault(s[r], 0) + 1
            while (cnt[s[r]]!! > 2) {
                cnt[s[l]] = cnt[s[l]]!! - 1
                l++
            }
            ans = maxOf(ans, r - l + 1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def maxLengthSubstring(self, s: str) -> int:
        from collections import defaultdict
        cnt: dict[str, int] = defaultdict(int)
        l = ans = 0
        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
16
17

impl Solution {
    pub fn max_length_substring(s: String) -> i32 {
        use std::collections::HashMap;
        let s = s.as_bytes();
        let mut cnt = HashMap::new();
        let (mut l, mut ans) = (0, 0);
        for r in 0..s.len() {
            *cnt.entry(s[r]).or_insert(0) += 1;
            while *cnt.get(&s[r]).unwrap() > 2 {
                *cnt.get_mut(&s[l]).unwrap() -= 1;
                l += 1;
            }
            ans = ans.max((r - l + 1) as i32);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    maxLengthSubstring(s: string): number {
        const cnt: Record<string, number> = {}
        let l = 0, ans = 0
        for (let r = 0; r < s.length; ++r) {
            cnt[s[r]] = (cnt[s[r]] ?? 0) + 1
            while (cnt[s[r]] > 2) {
                cnt[s[l]]--
                l++
            }
            ans = Math.max(ans, r - l + 1)
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s, since each character is processed at most twice.
  • 🧺 Space complexity: O(1), since the alphabet size is constant (at most 26 or 128 characters).