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;
    }
}

Last updated