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/
相关推荐
答案LeetCode-Longest_Substring_Without_Repeating_Characters 这是LeetCode上“最长子串无重复字符”问题的解决方案。 问题描述:给定一个字符串,求没有重复字符的最长子串的长度。 示例 1:输入:“abcabcbb” ...
大佬的leetcode刷题笔记(c++版本)
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...
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
LeetCode题解 - Java语言实现-181页.pdf
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
leetcode 答案最长子串 来自 leetcode.com 的问题。 描述: 给定一个字符串,找出没有重复字符的最长子字符串的长度。 示例 1: 输入:“abcabcbb” 输出:3 解释:答案是“abc”,长度为3。
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
leetcode1-300.docx
leetcode 答案leetcode--python Leetcode 的答案
leetcode 接口 该项目可帮助您使用首选的 IDE 或带有命令行界面 (CLI) 的编辑器来执行 leetcode。 入门 先决条件 Windows 10、MacOS、Linux Chrome版 >=90.0.4430 安装 # Prepare your virtual environment conda ...
leetcode 2 最长子串 给定一个字符串,找出没有重复字符的最长子字符串的长度。 示例 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. 示例 2: Input: "bbbbb" Output: ...
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。