2015年7月20日星期一

[LeetCode][面试未完成题目之魔咒] Longest Substring with At Most Two Distinct Characters

Problem:

Given a string S, find the length of the longest substring T that contains at most two distinct characters.
For example,
Given S = “eceba”,
T is “ece” which its length is 3.

Thinking:

维护一个变量 i,表示当前检测的substring ( with two distinct characters )的起始位置(k为终止位置)。
引入一个变量 j,表示更早结束出现的那一个character的最后一次出现的位置,这个变量是为了更新 i 而设置的,当 i 的值需要更新的时候(即遇到不是当前这两种字符的字符),i = j + 1,更新 i 的值之前更新maxLength。

举个例子(关于i,j,k的位置):

a b b a c c
i     j    k

a b b c c
i        k
j

Java Code:

public class Solution {
     public static int lengthOfLongestSubstringWithTwoDistinct(String s) {
         if (s == null || s.length() == 0) {
             return 0;
         }
         
         int i = 0;//start of current substring
         int j = -1;//更早结束出现的那一个字符最后一次出现的位置(为更新i使用)
         int maxLength = 0;
         
         for (int k = 1; k < s.length(); k++) {
             if (s.charAt(k) == s.charAt(k - 1)) {
                 continue;
             }
             
             if (j >= 0 && s.charAt(j) != s.charAt(k)) {
                 maxLength = Math.max(maxLength, k - i);
                 i = j + 1;
             }
             j = k - 1;
         }
         
         maxLength = Math.max(maxLength, s.length() - i);
         
         return maxLength;
     }
    
    
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstringWithTwoDistinct("aab"));
        System.out.println(lengthOfLongestSubstringWithTwoDistinct("aabb"));
        System.out.println(lengthOfLongestSubstringWithTwoDistinct("abbacc"));
        System.out.println(lengthOfLongestSubstringWithTwoDistinct("abbcc"));
        System.out.println(lengthOfLongestSubstringWithTwoDistinct("a"));
        System.out.println(lengthOfLongestSubstringWithTwoDistinct(""));
        System.out.println(lengthOfLongestSubstringWithTwoDistinct(null));
    }
}

reference: http://www.danielbit.com/blog/puzzle/leetcode/leetcode-longest-substring-with-at-most-two-distinct-characters

(脑洞:个人感觉这道题并不适合用“滑动窗口”的概念来解释,因为滑动窗口的感觉需要维护窗口的起始和终止两个变量的,而这道题目只需要维护一个变量i,因此一开始看sliding window的解释的时候很困惑,
关于滑动窗口协议:http://www.cnblogs.com/ulihj/archive/2011/01/06/1927613.html
更早结束出现的那一个character的最后一次出现的位置这句话说起来很拧巴,但是还没想出更好的表述)


没有评论:

发表评论