(Leetcode) Longest Substring with At Most Two Distinct Characters

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.

Solution 1:
Keep a sliding window of valid substring with at most 2 distinct characters. Keep track of the index of the last appearance of each of the 2 characters within the window. Use -1 as the default value of the index.

ai: the smaller index of the two last appearance indices
bi: the lager index of the two last appearance indices

We always have ai smaller than bi.

For example, in the example eceba, for window ece, the last appearance index for character c is 1, the last appearance for character e is 2. So here ai equals 1 and bi equals 2;

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int out = 0;
        int ai = -1, bi = -1;
        int start = 0;

        for (int i=0;i<s.size();i++) {
            if (ai == -1) {
                ai = i;
            } else if (bi == -1 && s[i] != s[ai]) {
                bi = i;
            } else if (bi == -1 && s[i] == s[ai]){
                ai = i;
            } else {
                if (s[i] != s[ai] && s[i] != s[bi]) {
                    // new char
                    start = ai + 1;
                    ai = bi;
                    bi = i;
                } else if (s[i] == s[ai]) {
                    ai = bi;
                    bi = i;
                } else {
                    bi = i;
                }
            }
            out = max(out,i-start+1);
        }

        return out;
    }
};

There is some improvement we could make to use only one index variable. But the current solution is easier to understand and has the same time complexity O(n).

Solution 2:
Instead of two indices, use a hashmap (or char array) to keep track of the last appearance index of a specific character.

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char,int> lasti;
        int out = 0, starti = 0, i = 0;

        for (;i<s.size();i++) {
            if (lasti.size()<2) {
                lasti[s[i]] = i;
            } else if (lasti.find(s[i]) != lasti.end()) {
                lasti[s[i]] = i;
            } else {
                out = max(out, i-1-starti+1);
                char frontc;
                int fronti = s.size();
                for (auto it = lasti.begin(); it != lasti.end(); it++) {
                    if (it->second < fronti) {
                        fronti = it->second;
                        frontc = it->first;
                    }
                }

                starti = fronti+1;
                lasti.erase(frontc);
                lasti[s[i]] = i;
            }
        }

        out = max(out, i-starti);
        return out;
    }
};