[Leetcode] Longest Substring with At Most 2 Distin

imccl 發(fā)布于2019-08-14 12:36 / 3538人閱讀

摘要：最新思路解法哈希表法復(fù)雜度時間空間思路我們遍歷字符串時用一個哈希表，但這個哈希表只記錄兩個東西，一個字母和它上次出現(xiàn)的時的下標(biāo)，另一個字母和它上次出現(xiàn)時候的下標(biāo)。這個通過用哈希表記錄字母上次出現(xiàn)的下標(biāo)，來維護一個窗口的方法也可以用于。

Longest Substring with At Most Two Distinct Characters 最新思路解法：https://yanjia.me/zh/2018/12/...

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.

哈希表法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

我們遍歷字符串時用一個哈希表，但這個哈希表只記錄兩個東西，一個字母和它上次出現(xiàn)的時的下標(biāo)，另一個字母和它上次出現(xiàn)時候的下標(biāo)。這樣，如果新來的字母已經(jīng)存在與表中，或者表中現(xiàn)在少于兩個字母，就沒關(guān)系，我們只要更新下它新的下標(biāo)就行了。如果不存在于表中，則找出表中兩個字母中，靠前面的那個，然后把這個較前的字母去掉，再加入這個新的字母。這樣，我們就能維護一個窗口，保證其中只有兩種字母。每次加入新字母時，說明上一個子串已經(jīng)達到最長了，這時候我們判斷下時候要更新全局最長子串就行了。這個通過用哈希表記錄字母上次出現(xiàn)的下標(biāo)，來維護一個窗口的方法也可以用于Longest Substring Without Repeating Characters。

注意

遍歷完之后還要一個額外判斷最長子串的代碼來處理最后一個子串

加入新字母后，新子串的起始位置是被除去字母最后一次出現(xiàn)位置的后一個

代碼

Java

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        String longestSubstr = "";
        int maxLength = 0, start = 0;
        HashMap map = new HashMap();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            // 如果表中已經(jīng)有兩個字母，且遇到了表中沒有的新字母時，加入新字母
            if(map.size() >= 2 && !map.containsKey(c)){
                int leftMost = s.length();
                // 先計算出新字母之前的子串的長度
                if(i - start > maxLength){
                    longestSubstr = s.substring(start, i);
                    maxLength = i - start;
                }
                // 找出哪個字母更靠前，將其去除
                for(Character key : map.keySet()){
                    if(map.get(key) maxLength){
            longestSubstr = s.substring(start, s.length());
            maxLength = s.length() - start;
        }
        return maxLength;
    }
}

func lengthOfLongestSubstringTwoDistinct(s string) int {
    chars := map[byte]int{}
    start := 0
    maxLength := 0
    for index := 0; index < len(s); index++ {
        char := s[index]
        if _, ok := chars[char]; !ok && len(chars) >= 2 {
            minIndex := len(s)
            for _, value := range chars {
                if value < minIndex {
                    minIndex = value
                }
            }
            start = minIndex + 1
            delete(chars, s[minIndex])
        }
        length := index - start + 1
        if maxLength < length {
            maxLength = length
        }
        chars[char] = index
    }
    return maxLength
}

后續(xù) Follow Up

Q：如果可以有k個distinct字母，怎么做？
A：將上題中的2換成k就行了。當(dāng)HashMap的大小大于k時，我們才將最早出現(xiàn)的字母移去。