[Leetcode] Longest Substring with At Most 2 Distin

imccl 發布于2019-08-14 12:36 / 3527人閱讀

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

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.

哈希表法 復雜度

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

思路

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

注意

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

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

代碼

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);
            // 如果表中已經有兩個字母，且遇到了表中沒有的新字母時，加入新字母
            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
}

后續 Follow Up

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

GPU云服務器云服務器 Most Longest LeetCode Substring

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64588.html

[LeetCode] 159. Longest Substring with At Most Two

Problem Given a string s , find the length of the longest substring t that contains at most 2 distinct characters. Example 1: Input: ecebaOutput: 3Explanation: t is ece which its length is 3.Example ...

geekidentity 2019-08-16 13:56 評論0 收藏0
159. Longest Substring with At Most Two Distinct C

摘要：表示某個最后一次出現的地方可能只包含一種或者兩種只包含一種強制保持出現兩種保證，為了計算方便出現第三種的時候，直接計算出當前長度。 Given a string, find the length of the longest substring T that contains at most 2 distinct characters. For example, Given s = e...

liujs 2019-08-16 10:35 評論0 收藏0
[leetcode] Minimum Window Substring

摘要：使用而不是因為我們需要的是最值，中間值我們不在乎，所以一次收斂到最小。下面來三個需要查重并且記錄上次出現的位置，選擇以為例，走到用做檢查，發現出現過，把移到的下一個。是上個題目的簡易版，或者特殊版。這里聊一聊解一類問題，就是滿足某一條件的substring最值問題。最開始我們以Minimum Window Substring為例，并整理總結leetcode里所有類似題目的通解。 Gi...

Pines_Cheng 2019-08-14 17:17 評論0 收藏0
159. Longest Substring With At Most Two Distinct C

摘要：題目解法最重要的是把最后一次出現的這個的記在的里面。所以當出現不止兩個的數的時候，把這個最低的刪掉，把最的加就可以啦題目：Given a string, find the length of the longest substring T that contains at most 2 distinct characters. For example, Given s = eceba...

spacewander 2019-08-14 14:12 評論0 收藏0
[Leetcode] Substring with Concatenation of All Wor

摘要：每次搜索中，我們通過哈希表維護一個窗口，比如中，我們先拿出。如果都不在數組中，那說明根本不能拼進去，則哈希表全部清零，從下一個詞開始重新匹配。 Substring with Concatenation of All Words You are given a string, s, and a list of words, words, that are all of the same...

adie 2019-08-14 12:46 評論0 收藏0