Longest Substring with At Most Two Distinct Characters

Hard, Array/String

给定字符串，寻找最多包含两个重复字符的最长子字符串。
P.S. 无重复字符串进阶版。

Example:
Given S = “eceba”,
T is "ece" which its length is 3.

Solution

建立一个移动窗口，窗口只能cover最多两个不同字符的字符串，当出现第三个character，调整窗口size使其只能cover最多两个不同字符。建立三个指针 i, j, k: i指向窗口的开头, k指向窗口的结尾，j控制窗口变化。

1. j首先使窗口cover两个不同字符。初始化为-1，当出现第二个不同字符是j指向第一个字符的最后出现的位置
2. 继续移动指针k, 如果出现第二个字符，继续更新k，i和j不变，如果出现第三个字符，更新当前最大长度为k-i。更新i的位置到第二个字符第一次出现的位置i=j+1
3. 因为最后的几个字符可能都是重复的，当前最大长度可能没有得到更新，补充max(len(s) - i, maxlen)。

P.S. 以上三步第n个字符针对窗口而言

complexity可以做到O(n)

class Solution(object):
    def lengthOfLongestSubstring2distinct(self, s):
        """
        :type s: str
        :rtype: int
        """
        i, j,maxlen = 0, -1, 0
   
        for k in xrange(1, len(s)):
            if s[k] = s[k-1]: continue
            if j > 0 and s[k] != s[j]:
                maxlen = max(k-i,maxlen)
                i = j+1
            j = k-1
        return max(len(s) - i, maxlen)
       ```
以上代码只能针对出现最多两字符，如果是最多`k`个字符呢?
此时我们需要一个计数器, 一旦出现多余`k`个字符，删除最早的字符并更新当前最大长度。一下代码的complexity是O(n^2)

class Solution(object):
def lengthOfLongestSubstring2distinct(self, s):
"""
:type s: str
:rtype: int
"""

count = {}
i, numDistinct = 0, maxlen = 0
for j in xrange(len(s):
    if count[s[j]] == 0: numDistinct += 1
    count[s[j]] += 1
    while numDistinct > k:
        count[s[i]] -= 1
        if count[s[i]] == 0: numDistinct -= 1
        i += 1
    maxlen = max(j - i +1, maxlen)
return maxlen