Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/159.html
Given a string s
, return the length of the longest substring that contains at most two distinct characters.
Example 1:
Input: s = "eceba" Output: 3 Explanation: The substring is "ece" which its length is 3.
Example 2:
Input: s = "ccaabbb" Output: 5 Explanation: The substring is "aabbb" which its length is 5.
Constraints:
1 <= s.length <= 105
s
consists of English letters.
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
-
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); // meaning last iteration is a valid result 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; } } } ############ class Solution { public int lengthOfLongestSubstringTwoDistinct(String s) { Map<Character, Integer> cnt = new HashMap<>(); int n = s.length(); int ans = 0; for (int i = 0, j = 0; i < n; ++i) { char c = s.charAt(i); cnt.put(c, cnt.getOrDefault(c, 0) + 1); while (cnt.size() > 2) { char t = s.charAt(j++); cnt.put(t, cnt.get(t) - 1); if (cnt.get(t) == 0) { cnt.remove(t); } } ans = Math.max(ans, i - j + 1); } return ans; } }
-
// 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; } };
-
''' >>> from collections import Counter >>> c = Counter() >>> c Counter() >>> c['a'] += 1 >>> c Counter({'a': 1}) >>> c Counter({'a': 1, 'c': 1, 'b': 1}) >>> c.pop(2) Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 2 >>> >>> c.pop('c') 1 >>> c Counter({'a': 1, 'b': 1}) ''' class Solution: def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int: cnt = Counter() # or, cnt = defaultdict(int) ans = i = 0 for j, c in enumerate(s): cnt[c] += 1 while len(cnt) > 2: cnt[s[i]] -= 1 if cnt[s[i]] == 0: cnt.pop(s[i]) i += 1 ans = max(ans, j - i + 1) 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
-
func lengthOfLongestSubstringTwoDistinct(s string) (ans int) { cnt := map[byte]int{} j := 0 for i := range s { cnt[s[i]]++ for len(cnt) > 2 { cnt[s[j]]-- if cnt[s[j]] == 0 { delete(cnt, s[j]) } j++ } ans = max(ans, i-j+1) } return } func max(a, b int) int { if a > b { return a } return b }