Longest Substring with At Most Two Distinct Characters - CPP Solution

1. Introduction

In this blog post, we explore an interesting problem in the realm of string processing and sliding window techniques in C++: finding the length of the longest substring that contains at most two distinct characters.

Problem

The challenge is to write a function in C++ that, given a string, finds the length of the longest substring containing at most two distinct characters.

2. Solution Steps

1. Use a sliding window approach to maintain a substring with at most two distinct characters.

2. Use a hash map to keep track of the count of each character within the window.

3. Expand the window from the right and add characters to the window.

4. If the window contains more than two distinct characters, shrink it from the left.

5. Update the maximum length of the substring each time the conditions are met.

6. Continue until the end of the string and return the maximum length found.

3. Code Program

#include <iostream>
#include <unordered_map>
using namespace std;

// Function to find the length of the longest substring with at most two distinct characters
int lengthOfLongestSubstringTwoDistinct(string s) {
    unordered_map<char, int> charCount;
    int left = 0, maxLength = 0;

    for (int right = 0; right < s.length(); right++) {
        // Add the current character to the window
        charCount[s[right]]++;

        // Shrink the window from the left if it contains more than two distinct characters
        while (charCount.size() > 2) {
            charCount[s[left]]--;
            if (charCount[s[left]] == 0) {
                charCount.erase(s[left]);
            }
            left++;
        }

        // Update the maximum length
        maxLength = max(maxLength, right - left + 1);
    }

    return maxLength;
}

int main() {
    string s = "eceba";
    cout << "Length of longest substring: " << lengthOfLongestSubstringTwoDistinct(s) << endl;
    return 0;
}

Output:

Length of longest substring: 3

Explanation:

1. The input string "eceba" is processed to find the longest substring with at most two distinct characters.

2. The sliding window approach is used to maintain a valid window of characters.

3. The window expands to include new characters, and shrinks when more than two distinct characters are found.

4. In this example, the longest valid substring is "ece", which has a length of 3.

5. The function efficiently calculates the maximum length while ensuring that the substring contains at most two distinct characters.