159. Longest Substring with At Most Two Distinct Characters.

1 暴力法

Time Limit Exceeded ``` class Solution(object): def lengthOfLongestSubstringTwoDistinct(self, s): """ :type s: str :rtype: int """ res = 0 n = len(s) if n < 3: return n

    for i in range(n - 1):
        dic = {}
        dic[s[i]] = 1
        for j in range(i + 1, n):
            if s[j] not in dic:
                dic[s[j]] = 1
            if len(dic) > 2:
                break

            res = max(res, j - i + 1)
    return res

## 分析
我们每次遇到第三个字符的时候，都回到 i 并移一位，这种做法是不是可以优化呢？

我们来看个例子：1 1 1 2 1 1 1 1 2 1 1 2 3

我们访问过第一个 1 之后，从第二个 1 开始，不可能比从第一个 1 开始搜索得到的长度更长。

那从第一个 2 开始呢？

也是不可能的，因为它之后还有 1 ，到 3 的时候，还是要比第一个 1 得到的长度短。

那么下一个下标从哪里开始呢？

答案是，从第三个字符往前看，找到前一个字符，如果前面是一组连续的相同的字符（连续的 1 或者连续的 2 都可以）的开始的位置。
当然，在实现的时候，我们会记录下来这个位置的前一位。下面看代码实现：


## Python

class Solution(object): def lengthOfLongestSubstringTwoDistinct(self, s): """ :type s: str :rtype: int """ res = 0 n = len(s) if n < 3: return n

    i = 1
    fc = 0 # begin of first char
    efc = 0 # end of first char
    sc = None

    while i < n:
        if s[fc] == s[i]: # if is the first character, continue
            efc = i
            i += 1
            continue

        if sc is None: # if is not the first character, and not found seconde character yet.
            sc = i
            i += 1
            continue

        if s[sc] == s[i]: # if is the second character
            sc = i
            i += 1
            continue

        res = max(res, i - fc) # a third character occurs, update the result.

        next_fc = min(efc, sc) + 1 # find the next first char.
        fc, efc, i = next_fc, next_fc, next_fc + 1 # update parameters.
        sc = None

    return max(res, i - fc) # in case, the longest substring in the end.

## C

int lengthOfLongestSubstringTwoDistinct(char* s) { if (strcmp(s, "") == 0) return 0; int fc = 0; int efc = 0; int i = 1; int sc = -1; int res = 0;

while (*(s + i) != '\0') {
    if (*(s + i) == *(s + fc)) {
        efc = i;
        i += 1;
        continue;
    }

    if ((sc == -1) | *(s + sc) == *(s + i)) {
        sc = i;
        i += 1;
        continue;
    }

    res = i - fc > res ? i - fc : res;

    int next_fc = 1 + (sc > efc ? efc : sc);

    fc = next_fc;
    efc = next_fc;
    sc = -1;
    i = next_fc + 1;
}

return i - fc > res ? i - fc : res;

} ```