0159. Longest Substring with At Most Two Distinct Characters
https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters
Description
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.
ac: sliding window
same as this one: https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/description/
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
// edge cases
if (s == null || s.length() == 0) return 0;
// build note
Map<Character, Integer> map = new HashMap<Character, Integer>();
int l = 0, r = 0, lgst = 0, cnt = 0;
// iterate
for (; r < s.length(); r++) {
char c = s.charAt(r);
map.put(c, map.getOrDefault(c, 0) + 1);
if (map.get(c) == 1) cnt++; // new character appear in current window
while (cnt > 2) { // one window formed
lgst = Math.max(lgst, r - l); // store length
char lc = s.charAt(l);
map.put(lc, map.get(lc) - 1);
l++; // remove left char, move window
if (map.get(lc) == 0) cnt--; // reduce one char count
}
}
lgst = Math.max(lgst, r - l); // update last window value
// result
return lgst;
}
}
Previous0158. Read N Characters Given Read4 II - Call multiple timesNext0160. Intersection of Two Linked Lists
Last updated
Was this helpful?