Longest SubString with At Most K Distinct Characters

Question

Given a string s, find the length of the longest substring T that contains at most k distinct characters.

Have you met this question in a real interview? Yes Example For example, Given s = "eceba", k = 3,

T is "eceb" which its length is 4.

Challenge O(n), n is the size of the string s.

Thoughts

类似longest substring without repeating characters

Solution

class Solution:
    # @param s : A string
    # @return : An integer
    def lengthOfLongestSubstringKDistinct(self, s, k):
        # write your code here
        map = {}
        i = 0
        j = 0
        ans = 0
        numDic = 0

        for i in range(len(s)):
            while j < len(s):
                if (s[j] in map and map[s[j]] != 0):
                    map[s[j]] += 1
                    ans = max(ans, j - i + 1)
                    j += 1
                elif numDic < k:
                    map[s[j]] = 1
                    numDic += 1
                    ans = max(ans, j - i + 1)
                    j += 1
                else:
                    break
            if s[i] in map:
                map[s[i]] -= 1 
                if map[s[i]] == 0:
                    numDic -= 1
        return ans