159. Longest Substring with At Most Two Distinct C

liujs 发布于2019-08-16 10:35 / 3355人阅读

摘要：表示某个最后一次出现的地方可能只包含一种或者两种只包含一种强制保持出现两种保证，为了计算方便出现第三种的时候，直接计算出当前长度。

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.

p1, p2 表示某个char最后一次出现的地方.
longest substring可能只包含一种char, 或者两种char.
1. 只包含一种Char, 强制保持p1 == p2
2. 出现两种char, 保证p1 <= p2， 为了计算方便
3. 出现第三种char的时候，i - (p1+1) + 1 = i- p1 直接计算出当前substring长度。同时保证p1<=p2.

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if(s == null || s.length() == 0) return 0;
        int p1 = 0, p2 = 0, len = 1, max = 1;
        char[] arr = s.toCharArray();
        for(int i = 1; i < arr.length; i++){
            // third char appear
            if(p1 != p2 && arr[i] != arr[p1] && arr[i] != arr[p2]){
                if(len > max) max = len;
                len = i - p1;
                p1 = p2;
                p2 = i;
            } else {
                // same char as p1 and p2
                if(arr[i] == arr[p1]){
                    p1 = p1 == p2 ? i : p2;
                }
                len++;
                p2 = i;
            }
        }
        if(len > max) max = len;
        return max;
    }
}

云服务器 GPU云服务器 cdn159 Most Longest Substring

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

转载请注明本文地址：https://www.ucloud.cn/yun/70087.html

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] 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
[Leetcode] Longest Substring with At Most 2 Distin

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

imccl 2019-08-14 12:36 评论0 收藏0
[leetcode] Minimum Window Substring

摘要：使用而不是因为我们需要的是最值，中间值我们不在乎，所以一次收敛到最小。下面来三个需要查重并且记录上次出现的位置，选择以为例，走到用做检查，发现出现过，把移到的下一个。是上个题目的简易版，或者特殊版。这里聊一聊解一类问题，就是满足某一条件的substring最值问题。最开始我们以Minimum Window Substring为例，并整理总结leetcode里所有类似题目的通解。 Gi...

Pines_Cheng 2019-08-14 17:17 评论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