Longest Substring with At Most Two Distinct Characters - rFronteddu/general_wiki GitHub Wiki

Longest Substring with At Most Two Distinct Characters. 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 "ece" contains at most 2 distinct characters and has length 3.

Example 2 Input: s = "ccaabbb" Output: 5 Explanation: The substring "aabbb" contains at most 2 distinct characters and has length 5.

import java.util.Map;
import java.util.HashMap;

class Main {
    public static void main(String[] args) {
        Map<Character, Integer> map = new HashMap<>(); 
        
        // max: 2
        //
        //  e: 1
        //  b: 1
        // 0  1  2  3  4
        // a, c, e, b, a
        //          r
        //       l
        
        String a = "ccaabbb";
        int maxSize = Integer.MIN_VALUE;
        int l = 0;
        int k = 2; // generalizes to k

        for(int r = 0; r < a.length(); r++) {
            char ca = a.charAt(r);
            map.put(ca, map.getOrDefault(ca, 0) + 1);
            
            while(map.keySet().size() > k) {
                char lc = a.charAt(l++);
                int count = map.get(lc) - 1;
                if(count == 0) map.remove(lc);
                else map.put(lc, count);
            }
            maxSize = Math.max(maxSize, r - l + 1);
        }
        System.out.println(maxSize);
    }
}