资讯专栏INFORMATION COLUMN

159. Longest Substring With At Most Two Distinct C

spacewander / 3008人阅读

摘要:题目解法最重要的是把最后一次出现的这个的记在的里面。所以当出现不止两个的数的时候,把这个最低的删掉,把最的加就可以啦

题目:
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.

解法:

//最重要的是把最后一次出现的这个char的index记在hashmap的value里面。所以当出现不止两个distinc的数的时候,把这个value最低的char删掉,把最lo的index加1就可以啦
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s.length() < 1) return 0;
        Map map = new HashMap();
        int lo = 0;
        int hi = 0;
        int maxLength = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (map.size() <= 2) {
                char c = s.charAt(i);
                map.put(c, i);
                hi++;
            }
            if (map.size() > 2) {
                int leftMost = s.length();
                for (int value : map.values()) {
                    leftMost = Math.min(leftMost, value);
                }
                lo = leftMost + 1;
                char c = s.charAt(leftMost);
                map.remove(c);
            }
            maxLength = Math.max(maxLength, hi - lo);
        }
        
        return maxLength;
    }

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

转载请注明本文地址:https://www.ucloud.cn/yun/64877.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 评论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 评论0 收藏0
  • [Leetcode] Longest Substring with At Most 2 Distin

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

    imccl 评论0 收藏0
  • [leetcode] Minimum Window Substring

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

    Pines_Cheng 评论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 评论0 收藏0

发表评论

0条评论

spacewander

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<