[LeetCode] 159. Longest Substring with At Most Two

geekidentity 发布于2019-08-16 13:56 / 2795人阅读

Problem

Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.

Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.
Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.

Solution

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null || s.length() == 0) return 0;
        Map map = new HashMap<>();
        int i = 0, j = 0, len = s.length(), max = 0;
        char[] str = s.toCharArray(); //char[] is much faster
        while (j < len) {
            map.put(str[j], j);
            j++;
            if (map.size() > 2) {
                int leftMost = len;
                for (int index: map.values()) leftMost = Math.min(leftMost, index);
                map.remove(str[leftMost]);
                i = leftMost+1;
            }
            max = Math.max(max, j-i);
        }
        return max;
    }
}

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

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

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

liujs 2019-08-16 10:35 评论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] 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