[Leetcode] Longest Substring with At Most 2 Distin

imccl 发布于2019-08-14 12:36 / 3314人阅读

摘要：最新思路解法哈希表法复杂度时间空间思路我们遍历字符串时用一个哈希表，但这个哈希表只记录两个东西，一个字母和它上次出现的时的下标，另一个字母和它上次出现时候的下标。这个通过用哈希表记录字母上次出现的下标，来维护一个窗口的方法也可以用于。

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时，我们才将最早出现的字母移去。

海外云主机云服务器 Most Longest LeetCode Substring

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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