[Leetcode] Longest Substr w/ At Most 2 Distinct Characters 双字母串

java 3 2016-02-29 13:03
女装

Longest Substring with At Most Two Distinct Characters

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

注意

  • 遍历完之后还要一个额外判断最长子串的代码来处理最后一个子串

  • 加入新字母后,新子串的起始位置是被除去字母最后一次出现位置的后一个

代码

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        String longestSubstr = "";
        int maxLength = 0, start = 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        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)<leftMost){
                        leftMost = map.get(key);
                    }
                }
                // 更新加入新字母后子串的起始位置,这个位置是被去除字母最后一次出现的位置加1
                start = leftMost + 1;
                map.remove(s.charAt(leftMost));
            }
            // 更新该字母下标
            map.put(c, i);
        }
        // 处理最后一个子串
        if(s.length() - start > maxLength){
            longestSubstr = s.substring(start, s.length());
            maxLength = s.length() - start;
        }
        return maxLength;
    }
}

后续 Follow Up

Q:如果可以有k个distinct字母,怎么做?
A:将上题中的2换成k就行了。当HashMap的大小大于k时,我们才将最早出现的字母移去。

女装
文章评论