Maximum Length Substring with Two Occurrences

Problem Statement

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:

Input: s = “bcbbbcba”

Output: 4

Explanation:

The following substring has 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.

Different Approaches

1 Sliding Window

Algorithm:

1. Initialize variables left and right to represent the left and right boundaries of the window, and a hashmap count to store the count of characters in the window.
2. Iterate through the string s:
   1. Increment the count of the character at index right.
   2. If the count of characters in the window exceeds 2, shrink the window from the left until the count is 2.
   3. Update the maximum length of the window.
3. Return the maximum length of the window.

Code Implementation C++:

#include <iostream>
#include <string>
#include <map>

using namespace std;

int maxLengthSubstringWithTwoOccurrences(string s) {
    int n = s.size(), ans = 0, begin = 0, end = 0;
    map<char, int> mp;

    while (end < n) {
        mp[s[end]]++;
        // Shrink the window until there are at most two occurrences of each character
        while (mp[s[end]] == 3)
            mp[s[begin++]]--;
        // Update the maximum length of the substring
        ans = max(ans, end - begin + 1);
        end++;
    }
    return ans;
}

int main() {
    string s1 = "ccaabbb";
    string s2 = "aaa";

    cout << "Maximum length of substring with two occurrences (s1): " << maxLengthSubstringWithTwoOccurrences(s1) << endl;
    cout << "Maximum length of substring with two occurrences (s2): " << maxLengthSubstringWithTwoOccurrences(s2) << endl;

    return 0;
}

Explanation:

1 Initialization:

int n = s.size(), ans = 0, begin = 0, end = 0;
map<char, int> mp;

• n: stores the size of the input string s.
• ans: Initialized to 0 to store the maximum length of the substring with most two occurrences of each character.
• begin and end: Pointers to represent the window boundaries.
• mp: A map to store the count of occurrences of each character in the current window.

2 Sliding Window Approach:

while (end < n) {
    mp[s[end]]++;
    // Shrink the window until there are at most two occurrences of each character
    while (mp[s[end]] == 3)
        mp[s[begin++]]--;
    // Update the maximum length of the substring
    ans = max(ans, end - begin + 1);
    end++;
}

• We iterate through the string using the end pointer.
• At each step, we update the count of the character at index end in the mp map.
• If the count of the character exceeds two (indicating more than two occurrences), we shrink the window from the begin pointer until there are at most two occurrences of each character.
• We update the maximum length of the substring ans with the maximum length found so far.
• Finally, we move the end pointer to expand the window.

3 Returning the Result:

return ans;

• Once we have iterated through the entire string and updated the maximum length of the substring ans, we return it.