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

// Source : https://oj.leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
// Author : Hao Chen
// Date   : 2014-12-01

/*
 * Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
 * 
 * For example, Given s = “eceba”,
 * 
 * T is "ece" which its length is 3.
 */



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


/*
 * Idea:
 *
 *    1) Using a map to count every char(s).
 *    2) Using a 'cnt' to count the current distinct chars.
 *    3) If `cnt > 2`, then go through the previous substring to decrease each char's count which stored in the map,
 *       if one of char's count decrease to zero, then the global distinct chars `cnt` decrease one.
 *       During the travel, maintain a pointer `start` to point the start position of sub-string.
 *
 * The following algorithm run-time complexity is O(n^2)
 *
 * This solution can be easy to extend to "find the length of longest substring with at most K distinct char(s)"
 */
int lengthOfLongestSubstringTwoDistinct(string s) {
    int maxLen = 0;
    int charMap[256] = {0};
    int wordCnt = 0;
    int start = 0;

    for(int i=0; i<s.size(); i++){
        if ( charMap[s[i]]++ == 0 ){
            wordCnt++;
        }
        while (wordCnt>2){
            charMap[s[start]]--;
            if (charMap[s[start]]==0){
                wordCnt--;
            }
            start++;
        }
        maxLen = max(maxLen, i - start + 1);
    }

    return maxLen;
}


int main(int argc, char** argv)
{
    string s = "eceba";
    if (argc>1){
        s = argv[1];
    }
    cout << s << " : " << lengthOfLongestSubstringTwoDistinct(s) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/description/
/// Author : liuyubobobo
/// Time   : 2016-12-30

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cassert>
#include <cmath>

using namespace std;


/// Two Pointers + HashMap
/// Recording how many different characters in the current string by map.
///
/// Time Complexity:  O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {

        unordered_map<char, int> map;
        int l = 0, r = 0;
        int res = 0;
        while(r <= s.size()){
            if(r == s.size() || (map.size() == 2 && map.find(s[r]) == map.end())){
                res = max(res, r-l);
                while(map.size() >= 2){
                    if(map[s[l]] == 1)
                        map.erase(s[l]);
                    else
                        map[s[l]] --;
                    l ++;
                }

                if( r == s.size() )
                    break;
            }
            else{
                if(map.find(s[r]) == map.end())
                    map[s[r]] = 1;
                else
                    map[s[r]] += 1;
                r ++;
            }
        }

        return res;
    }
};


int main() {

    cout << Solution().lengthOfLongestSubstringTwoDistinct("eceba") << endl;
    cout << Solution().lengthOfLongestSubstringTwoDistinct("a") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/description/
/// Author : liuyubobobo
/// Time   : 2017-03-01
#include <iostream>
#include <vector>
#include <unordered_map>
#include <cassert>
#include <cmath>

using namespace std;


/// Two Pointers + Static Array as HashMap
/// Using self-built hashtable to record how many different characters in the current string
///
/// Time Complexity:  O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {

        int hashtable[256] = {0};
        int l = 0, r = 0;
        int res = 0;
        int count = 0;
        while(r <= s.size()){
            if(r == s.size() || (count == 2 && !hashtable[s[r]])){
                res = max(res, r-l);
                while(count >= 2){
                    hashtable[s[l]] --;
                    if(hashtable[s[l]] == 0)
                        count --;
                    l ++;
                }

                if(r == s.size())
                    break;
            }
            else{
                hashtable[s[r]] ++;
                if(hashtable[s[r]] == 1)
                    count ++;
                r ++;
            }
        }

        return res;
    }
};

int main() {

    cout << Solution().lengthOfLongestSubstringTwoDistinct("eceba") << endl;
    cout << Solution().lengthOfLongestSubstringTwoDistinct("a") << endl;

    return 0;
}