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的最后一次出现的位置这句话说起来很拧巴,但是还没想出更好的表述)
没有评论:
发表评论