340. Longest Substring with At Most K Distinct Characters

最后更新

二刷
08-Jan-2017

和76、159很像。。

2 pointers.. 通过判断是否每一次是有效读取来增减accumulator，从而判断当前是否符合规定，再来更新maxLength

Time: O(n)
Sapce : O(1)

public class Solution {
    
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s.length() == 0 || k == 0) return 0;
        
        int[] chars = new int[256];
        int temp = 0;
        int right = 0;
        int maxLength = -1;
        
        for (int left = 0; left < s.length(); left ++) {
            while (right < s.length()) {
                // next read will be valid read, will make cumulator ++, since we cannot
                // tolerate more dinstince chars by temp == k, we shall break at thsi point
                if (temp == k && chars[s.charAt(right)] == 0) {
                    break;
                }
                
                if (++chars[s.charAt(right++)] == 1) {
                    temp ++;
                }
            }
            
            if (right - left > maxLength && temp <= k) {
                maxLength = right - left;
            }
            if (--chars[s.charAt(left)] == 0) {
                temp --;
            }
        }
        return maxLength;
       
    }
}

---

一刷
18-Dec-2016

做过一个很类似的，记不清了。

维持窗口，用map记录出现字符的最后位置，超过K的时候从最左删一个。。更新大小。。

这也是HARD难度的么。。

public class Solution 
{
    public int lengthOfLongestSubstringKDistinct(String s, int k) 
    {
        if(k == 0 || s.length() == 0) return 0;
        
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        
        int res = 1;
        int temp = 0;
        int l = 0;
        
        
        for(int i = 0; i < s.length(); i++)
        {
            char c = s.charAt(i);
            
            if(map.containsKey(c))
            {
                map.put(c,i);
                
            }
            else
            {
                
                map.put(c,i);
                temp++;
                if(temp > k)
                {
                    char tempK = c;
                    int index = i;
                    Iterator iter = map.keySet().iterator();
                    while(iter.hasNext())
                    {
                        char key = (char)iter.next();
                        if(index > map.get(key))
                        {
                            tempK = key;
                            index = map.get(key);
                        }

                    }
                    map.remove(tempK);
                    l = index + 1;
                    temp--;
                }
            }
            res = Math.max(res,i+1-l);
        }
        
        
        return res;
    }
}