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.
[分析]
brute force的解法就是构造出来所有substring然后线性扫描一遍,复杂度为O(n^3)。可以使用Set来判断是不是有重复的字符。如果假定是在26个英文字母之间的话,更容易了,直接上个array就好。但这个假定一般都不会成立的。
最优的解法应该是维护一个sliding window,指针变量i指向sliding window的起始位置,j指向另个一个字符在sliding window的最后一个,用于定位i的下一个跳转位置。内部逻辑就是
1)如果当前字符跟前一个字符是一样的,直接继续。
2)如果不一样,则需要判断当前字符跟j是不是一样的
a)一样的话sliding window左边不变,右边继续增加,但是j的位置需要调整到k-1。
b)不一样的话,sliding window的左侧变为j的下一个字符(也就是去掉包含j指向的字符的区间),j的位置也需要调整到k-1。
在对i进行调整的时候(1.a),需要更新maxLen。
[注意事项]
1)在最后返回的时候,注意考虑s.length()-i这种情况,也就是字符串读取到最后而没有触发(1.a)
2)讲解清楚sliding window的更新
3)该题目有个follow-up,就是如果是k个distinct characters怎么办。这样的话就只能对所有可能的字符用一个数组去做counting,而且只能假设ASIC字符集256。Unicode太大了。
public int lengthOfLongestSubstringTwoDistinct(String s) { int i = 0, j = -1, maxLen = 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)) { maxLen = Math.max(k - i, maxLen); i = j + 1; } j = k - 1; } return Math.max(s.length() - i, maxLen); }
上面方法的变量名实在是太难理解了,重写了一遍,下面这个更好理解。
public int lengthOfLongestSubstringTwoDistinct(String s) { int left = 0, second = -1; int n = s.length(); int len = 0; for(int i=1; i < n; i++) { if(s.charAt(i) == s.charAt(i-1)) continue; if(second >= 0 && s.charAt(i) != s.charAt(second)) { len = Math.max(len, i-left); left = second+1; } second = i-1; } return Math.max(len, n-left); }
Follow up (K distinct characters):
public int lengthOfLongestSubstringKDistinct(String s, int k) { int len = 0, n = s.length(); int left = 0, right = 0; // the start and end position of first char Map<Character, Integer> map = new HashMap<>(); for(int i=0; i<n; i++) { char c = s.charAt(i); if(map.containsKey(c) || map.size() < k) { if(s.charAt(left) == c) right = i; } else { len = Math.max(len, i-left); map.remove(s.charAt(left)); left = right = right + 1; if(k > 1) right = map.get(s.charAt(left)); } map.put(c, i); } return Math.max(len, n-left); }
滑动窗口的解法,这次HashMap里面的value存的不再是字符出现的最后一次索引,而是字符出现的次数。
public int lengthOfLongestSubstringKDistinct(String s, int k) { int len = 0, n = s.length(); int left = 0; Map<Character, Integer> map = new HashMap<>(); for(int i=0; i<n; i++) { char c = s.charAt(i); Integer cnt = map.get(c); if(cnt == null) cnt = 0; map.put(c, cnt+1); while(map.size() > k) { char key = s.charAt(left++); int val = map.get(key)-1; if(val == 0) { map.remove(key); } else { map.put(key, val); } } len = Math.max(len, i-left+1); } if(map.size() < k) return 0; return Math.max(len, n-left); }
Reference:
http://www.programcreek.com/2013/02/longest-substring-which-contains-2-unique-characters/
http://www.geeksforgeeks.org/find-the-longest-substring-with-k-unique-characters-in-a-given-string/
相关推荐
java java_leetcode题解之Longest Substring with At Most Two Distinct
c语言入门 c语言_leetcode题解03-longest-substring-without-repeating-characters
js js_leetcode题解3-longest-substring-without-repeating-characters.js
c c语言_leetcode 0003_longest_substring_without_repeat.zip
c c语言_leetcode 0005_longest_palindromic_substring.zip
c c语言_leetcode 0011_container_with_most_water.zip
c语言入门 c语言_leetcode题解05-longest-palindromic-substring.c
c c语言_leetcode 0014_longest_common_prefix.zip
c c语言_leetcode 0030_substring_with_concatenation_of_all_words.zip
答案LeetCode-Longest_Substring_Without_Repeating_Characters 这是LeetCode上“最长子串无重复字符”问题的解决方案。 问题描述:给定一个字符串,求没有重复字符的最长子串的长度。 示例 1:输入:“abcabcbb” ...
java java_leetcode题解之Longest Substring Without Repeating
js js_leetcode题解之5-longest-palindromic-substring.js
5. leetCode-5-Longest-Palindromic-Substring.md:第5题,最长回文子串,考察字符串处理和动态规划。 6. leetCode-84-Largest-Rectangle-in-Histogram.md:第84题,柱状图中最大的矩形,涉及到数组处理和栈的数据...
java入门 java_leetcode题解之003_Longest_Substring_Without_Repeating
java入门 java_leetcode题解之005_Longest_Palindromic_Substring
《LeetCode---C++实现》是一本专注于C++编程语言解决LeetCode在线判题平台上的算法问题的书籍。LeetCode是程序员广泛使用的平台,它提供了大量的编程题目来提升编程技能和算法理解,尤其对于准备面试的程序员来说,...
js js_leetcode题解之30-substring-with-concatenation-of-all-words.js
Longest-Palindromic-Substring(最长回文子串) 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 Sample 1 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 Sample 2 输入...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
c语言入门 c语言_leetcode题解leftmost-column-with-at-least-a-one.c