159. Longest Substring with At Most Two Distinct Characters

最后更新

二刷

08-Jan-17

回头看了下一刷的，用的map,应该是int[256]的意思，后面没仔细看cuz whatever I was doing at that time.. wasnt good

做法和LC 76非常像，用2 Pointers + 计数来判断是否满足。

这里“有效读取”的判断标准变成了 count[s.charAt(someIndex)]是否从0递增，和每个循环最后它是否递减回0，以此判断dinstinct是否有变化，其实这个比76的有效读取要稍微好理解一些。

Time: O(N)

Space: Constant space..

public class Solution {

    public int lengthOfLongestSubstringTwoDistinct(String s) {

        if (s.length() <= 2) return s.length();

        int[] count = new int[256];

        int temp = 0;

        int right = 0;

        int maxLength = -1;

        for (int left = 0; left < s.length(); left ++) {

            while (right < s.length()) {

                if (temp == 2 && count[s.charAt(right)] == 0) break;

                if (++count[s.charAt(right++)] == 1) {

                    temp ++;

                }

            }

            if (right - left > maxLength) {

                maxLength = right - left;

            }

            if (--count[s.charAt(left)] == 0) {

                temp --;

            }

        }

        return maxLength;

    }

}

一刷

18-Dec-2016

怎么和上一题一样的。。。

map快。。

import java.util.Hashtable;

public class Solution

{

    public int lengthOfLongestSubstringTwoDistinct(String s)

    {

        if(s.length() <= 2) return s.length();

        Hashtable<Character,Integer> table = new Hashtable<Character,Integer>();

        int temp = 0;

        int l = 0;

        int res = 1;

        for(int i = 0; i < s.length();i++)

        {

            char c = s.charAt(i);

            if(!table.containsKey(c)) temp++;

            table.put(c,i);

            if(temp > 2)

            {

                temp--;

                Iterator iter = table.keySet().iterator();

                char iterC = c;

                int index = i;

                while(iter.hasNext())

                {

                    char tempC = (char)iter.next();

                    if(table.get(tempC) < index)

                    {

                        index = table.get(tempC);

                        iterC = tempC;

                    }

                }

                table.remove(iterC);

                l = index + 1;

            }

            res = Math.max(res,i+1-l);

        }

        return res;

    }

}

巴特西

159. Longest Substring with At Most Two Distinct Characters

最新文章

热门文章