[LeetCode]Longest Substring with At Most Two Distinct Characters

仍然是双指针，维护一个map，这里substring只允许最多两个distinct characters，左指针根据右指针移动的策略是：

• 若右指针指向的字符在map内，更新map，看有没需要更新返回的substring
• 若右指针指向的字符不在map里，更新map，如果map的size小于等于2，看有没需要更新返回的substring
• 若右指针指向的字符不在map里，更新map，如果map的size大于2，右移左指针直到map的size小于等于2，看有没需要更新返回的substring

时间复杂度是O(n)，代码如下：

	public class Solution {
	public int lengthOfLongestSubstringTwoDistinct(String s) {
	if (s == null)
	return 0;
	int len = s.length();
	HashMap<Character, Integer> map = new HashMap<Character, Integer>();
	int left = 0, maxLen = 0;
	for (int right = 0; right < len; right++) {
	char curr = s.charAt(right);
	if (map.containsKey(curr))
	map.put(curr, map.get(curr) + 1);
	else {
	map.put(curr, 1);
	while (map.size() > 2) {
	char temp = s.charAt(left);
	map.put(temp, map.get(temp) - 1);
	if (map.get(temp) == 0)
	map.remove(temp);
	left++;
	}
	}
	if (right - left + 1 > maxLen)
	maxLen = right - left + 1;
	}
	return maxLen;
	}
	}

view raw Longest Substring with At Most Two Distinct Characters.java hosted with ❤ by GitHub