# Maximum Length Substring With Two Occurrences
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-length-substring-with-two-occurrences)
Canonical: https://scaleengineer.com/dsa/problems/maximum-length-substring-with-two-occurrences
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Hash Table, String
---
## Problem
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.

# Approaches
## Brute-Force with Substring Check
This approach systematically checks every possible substring of the input string `s`. For each substring, it verifies if it meets the condition: containing at most two occurrences of each character. It keeps track of the length of the longest valid substring found.
**Time:** O(n^2), where n is the length of the string `s`. The nested loops iterate through approximately n^2/2 substrings, and the operations inside the inner loop take constant time. · **Space:** O(1) or O(k), where k is the number of unique characters in the alphabet (26 in this case). A new frequency map is created for each starting position `i`, but its size is constant.
**Pros:** Straightforward and easy to understand.; Correctly solves the problem for the given constraints.
**Cons:** Inefficient for large input strings due to its quadratic time complexity.; It re-checks many overlapping substrings, leading to redundant computations.
### Explanation
The algorithm uses two nested loops to generate all substrings. The outer loop, with index `i`, fixes the starting point of the substring. The inner loop, with index `j`, extends the substring to the right, one character at a time.

For each starting point `i`, a new frequency map (an array of size 26) is initialized to count character occurrences for substrings starting at `i`. As the inner loop progresses, we add `s.charAt(j)` to the current substring and update its frequency. We then check if this character's count has exceeded 2. If it has, the substring `s.substring(i, j + 1)` is invalid. Since any longer substring starting at `i` will also be invalid, we can break the inner loop and proceed to the next starting position `i + 1`.

If the character count is valid (i.e., less than or equal to 2), the current substring `s.substring(i, j + 1)` is valid, and we update our `maxLength` with its length if it's the largest seen so far.

```java
class Solution {
    public int maximumLengthSubstring(String s) {
        int maxLength = 0;
        int n = s.length();
        if (n == 0) {
            return 0;
        }

        for (int i = 0; i < n; i++) {
            int[] counts = new int[26];
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                counts[c - 'a']++;
                if (counts[c - 'a'] > 2) {
                    // The substring from i to j is invalid, so any longer substring starting at i will also be invalid.
                    break;
                }
                // The substring from i to j is valid.
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`.
- Iterate through the string with an index `i` from `0` to `n-1` to define the start of the substring.
- Inside this loop, create a frequency map `counts` (e.g., an integer array of size 26 for lowercase English letters).
- Start a nested loop with an index `j` from `i` to `n-1` to define the end of the substring.
- In the inner loop, get the character `c = s.charAt(j)` and increment its count in the `counts` map.
- Check if the count of `c` has become greater than 2.
- If `counts[c - 'a'] > 2`, the current substring `s.substring(i, j + 1)` and any further extensions from `i` are invalid. Break the inner loop.
- If the count is valid (<= 2), update the maximum length: `maxLength = Math.max(maxLength, j - i + 1)`.
- After the loops complete, return `maxLength`.

## Optimal Sliding Window
A more optimal solution uses the sliding window technique. This approach maintains a 'window' (a substring) that is always valid or is immediately corrected to become valid. The window expands by moving a `right` pointer and shrinks by moving a `left` pointer, ensuring the condition of at most two occurrences per character is met. This avoids re-computation by efficiently updating the window in a single pass over the string.
**Time:** O(n), where n is the length of the string `s`. Each pointer, `left` and `right`, traverses the string at most once. This results in a single pass and linear time performance. · **Space:** O(1) or O(k), where k is the size of the character set (26). The frequency map has a fixed size, independent of the input string's length.
**Pros:** Optimal time complexity of O(n).; Efficient in terms of space, using only a constant amount of extra space.; Scales well even for much larger strings.
**Cons:** The logic can be slightly more complex to reason about compared to a simple brute-force approach.
### Explanation
We use two pointers, `left` and `right`, to define the current window `s.substring(left, right + 1)`. We also use a frequency map, `counts`, to store character frequencies within this window.

The `right` pointer iterates from the beginning to the end of the string to expand the window. At each step, we add `s.charAt(right)` to the window and increment its count.

If adding `s.charAt(right)` causes its count to become 3, the window becomes invalid. To fix this, we shrink the window from the left by moving the `left` pointer to the right. We decrement the count of the character at the `left` pointer and advance `left`. We repeat this shrinking process until the count of `s.charAt(right)` is back to 2, making the window valid again.

After each step of the `right` pointer (and any necessary shrinking), the current window `s.substring(left, right + 1)` is guaranteed to be valid. We then update our `maxLength` with the length of this current valid window. This single pass ensures linear time complexity.

```java
class Solution {
    public int maximumLengthSubstring(String s) {
        int[] counts = new int[26];
        int left = 0;
        int maxLength = 0;
        int n = s.length();

        for (int right = 0; right < n; right++) {
            char charRight = s.charAt(right);
            counts[charRight - 'a']++;

            // If the count of the character just added exceeds 2, 
            // we need to shrink the window from the left until its count is valid again.
            while (counts[charRight - 'a'] > 2) {
                char charLeft = s.charAt(left);
                counts[charLeft - 'a']--;
                left++;
            }

            // The window s[left..right] is now valid.
            // Update the maximum length found so far.
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}
```
### Algorithm
- Initialize a frequency map `counts` (an array of size 26), a `left` pointer to 0, and `maxLength` to 0.
- Iterate through the string with a `right` pointer from `0` to `n-1`.
- For each character `charRight = s.charAt(right)`, increment its count in the `counts` map.
- Enter a `while` loop that checks if the count of `charRight` has exceeded 2.
- Inside the `while` loop, shrink the window from the left: decrement the count of `s.charAt(left)` and increment the `left` pointer.
- The loop continues until the window is valid again (i.e., the count of `charRight` is no more than 2).
- After the window is guaranteed to be valid, calculate its current length `right - left + 1` and update `maxLength`.
- After the `for` loop finishes, return `maxLength`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```