Question
Formatted question description: https://leetcode.ca/all/159.html
159 Longest Substring with At Most Two Distinct Characters
Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.
Example 1:
Input: "eceba"
Output: 3
Explanation: tis "ece" which its length is 3.
Example 2:
Input: "ccaabbb"
Output: 5
Explanation: tis "aabbb" which its length is 5.
@tag-string
@tag-2pointers
Algorithm
Use HashMap to do it, HashMap records the number of occurrences of each character,
Then if the number of mappings in HashMap exceeds two, one mapping needs to be deleted here.
For example "eceba"
, there are 2 e
in the HashMap and 1 c
in the HashMap. At this time, b
is also stored in the HashMap, then there are three pairs of mappings. At this time, left is 0, and the mapping value is reduced by 1. There is one more e
, do not delete it, and left is incremented by 1. At this time, there are three pairs of mappings in the HashMap. At this time, left is 1, then c
is reached, and the mapping value is reduced by 1. At this time, e
is mapped to 0, e
is deleted from the HashMap, left is incremented by 1, and the result is updated to i - left + 1
.
And so on until the entire string is traversed.
Code
Java
-
import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; public class Longest_Substring_with_At_Most_Two_Distinct_Characters { public static void main(String[] args) { Longest_Substring_with_At_Most_Two_Distinct_Characters out = new Longest_Substring_with_At_Most_Two_Distinct_Characters(); Solution s = out.new Solution(); System.out.println(s.lengthOfLongestSubstringTwoDistinct("eceba")); System.out.println(s.lengthOfLongestSubstringTwoDistinct("ccaabbb")); } // refer to: // Longest_Substring_with_At_Most_K_Distinct_Characters public class Solution { /** * @param s: a string * @return: the length of the longest substring T that contains at most 2 distinct characters */ public int lengthOfLongestSubstringTwoDistinct(String s) { if (s == null || s.length() == 0) { return 0; } // char => its count in window Map<Character, Integer> map = new HashMap<>(); int maxLen = 0; int left = 0; int right = 0; while (right < s.length()) { char c = s.charAt(right); if (map.containsKey(c)) { map.put(c, map.get(c) + 1); } else { map.put(c, 1); } // if distinct chars more than k if (map.size() > 2) { maxLen = Math.max(maxLen, right - left); // shrink the window size while (map.size() > 2) { // can be done by another counter variable char leftChar = s.charAt(left); int freq = map.get(leftChar); if (freq == 1) { map.remove(leftChar); // @note: remove by key } else { map.put(leftChar, freq - 1); } left++; } } right++; } // @note: final check if (left < s.length()) { maxLen = Math.max(maxLen, right - left); } return maxLen; } } public class Solution_arrayAsMap { public int lengthOfLongestSubstringTwoDistinct(String s) { int[] countMap = new int[256]; Set<Character> hs = new HashSet<>(); int result = 0; int left = 0; int right = 0; while (right < s.length()) { char c = s.charAt(right); countMap[c]++; hs.add(c); if (hs.size() > 2) { result = Math.max(result, right - left); while (hs.size() > 2) { if (--countMap[s.charAt(left)] == 0) { hs.remove(s.charAt(left)); } left++; } } right++; } // @note: final check if (left < s.length()) { result = Math.max(result, right - left); } return result; } } }
-
// OJ: https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/ // Time: O(N) // Space: O(C) class Solution { public: int lengthOfLongestSubstringTwoDistinct(string s) { vector<int> m(128, 0); int i = 0, j = 0, ans = 0, cnt = 0; while (j < s.size()) { if (m[s[j++]]++ == 0) ++cnt; while (cnt > 2) { if (m[s[i++]]-- == 1) --cnt; } ans = max(ans, j - i); } return ans; } };
-
class Solution(object): def lengthOfLongestSubstringTwoDistinct(self, s): """ :type s: str :rtype: int """ return self.lengthOfLongestSubstringKDistinct(s, 2) def lengthOfLongestSubstringKDistinct(self, s, k): """ :type s: str :type k: int :rtype: int """ if k == 0: return 0 ans = 0 j = 0 score = 0 chashmap = {} for i in range(0, len(s)): while j < len(s) and (score < k or chashmap.get(s[j], 0) != 0): if chashmap.get(s[j], 0) == 0: score += 1 chashmap[s[j]] = chashmap.get(s[j], 0) + 1 j += 1 ans = max(ans, j - i) chashmap[s[i]] -= 1 if chashmap[s[i]] == 0: score -= 1 return ans