首页 > 代码库 > Longest Substring with At Most Two Distinct
Longest Substring with At Most Two Distinct
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is "ece" which its length is 3.
用p1 & p2 两个pointer分别纪录当前window里两个character最后一次发生时的index，用start纪录window开始时的index。
从index 0开始遍历String:
如果当前的character在window内，update相应的pointer。
如果不在，比较两个character的pointer，去掉出现较早的那个character, 更新start=min(p1,p2)+1
时间复杂度是O(n), 空间复杂度是O(1):
1 public class Solution { 2 public int lengthOfLongestSubstringTwoDistinct(String s) { 3 int result = 0; 4 int first = -1, second = -1; 5 int win_start = 0; 6 for(int i = 0; i < s.length(); i ++){ 7 if(first < 0 || s.charAt(first) == s.charAt(i)) first = i; 8 else if(second < 0 || s.charAt(second) == s.charAt(i)) second = i; 9 else{10 int min = first < second ? first : second;11 win_start = min + 1;12 if(first == min) first = i;13 else second = i;14 }15 result = Math.max(result, i - win_start + 1);16 }17 return result;18 }19 }
Longest Substring with At Most Two Distinct
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。