Longest Substring with At Most Two Distinct Characters in C++

Suppose we have a string s; we have to find the length of the longest substring t that has at most 2 distinct characters.

So, if the input is like "eceba", then the output will be 3 as t is "ece" which its length is 3.

To solve this, we will follow these steps −

• Define a function lengthOfLongestSubstringKDistinct(), this will take s, k,

• ans := 0

• Define one map m

• n := size of s, x := 0

• for initialize j := 0, i := 0, when j < n, update (increase j by 1), do −

  • (increase m[s[j]] by 1)

  • if m[s[j]] is same as 1, then −

    • (increase x by 1)

  • while (x > k and i <= j), do −

    • (decrease m[s[i]] by 1)

    • if m[s[i]] is same as 0, then −

      • (decrease x by 1)

    • (increase i by 1)

  • ans := maximum of ans and j - i + 1

• return ans

• From the main method do the following

• return lengthOfLongestSubstringKDistinct(s, 2)

Example 

Let us see the following implementation to get better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution { public:    int lengthOfLongestSubstringKDistinct(string s, int k){       int ans = 0;       unordered_map<char, int> m;       int n = s.size();       int x = 0;       for (int j = 0, i = 0; j < n; j++) {          m[s[j]]++;          if (m[s[j]] == 1)             x++;          while (x > k && i <= j) {             m[s[i]]--;             if (m[s[i]] == 0)                x--;             i++;          }          ans = max(ans, j - i + 1);       }       return ans;    }    int lengthOfLongestSubstringTwoDistinct(string s){       return lengthOfLongestSubstringKDistinct(s, 2);    } }; main(){    Solution ob;    cout << (ob.lengthOfLongestSubstringTwoDistinct("eceba")); }

Input

"eceba"

Output

3