159. Longest Substring with At Most Two Distinct Characters

Description

Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: "eceba"

Output: 3

Explanation: t is "ece" which its length is 3.

Example 2

Input: "ccaabbb"

Output: 5

Explanation: t is "aabbb" which its length is 5.

Solutions

Solution 1

/**
 * Time complexity : O(N)
 * Space complexity : O(1)
 */

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int result = 0;
        if(s == null || s.length() == 0) return result;
        
        int n = s.length(), start = 0;
        Map<Character, Integer> countMap = new HashMap();
        
        // At Most Two Distinct Characters
        int k = 2;
        
        for(int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            countMap.put(ch, countMap.getOrDefault(ch, 0)+1);
            
            if(countMap.size() <= k) {
                result = Math.max(result, i-start+1);
            } else {
                while(countMap.size() > k) {
                    ch = s.charAt(start);
                    int count = countMap.get(ch);
                    if(count == 1) {
                        countMap.remove(ch);
                    } else {
                        countMap.put(ch, count-1);
                    }
                    start++;
                }
            }
        }
        
        return result;
    }
}

Solution 2

/**
 * Time complexity : O(N)
 * Space complexity : O(1)
 */

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int result = 0;
        if(s == null || s.length() == 0) return result;
        
        int n = s.length(), start = 0, distinct = 0;
        
        int[] countMap = new int[256];
        Arrays.fill(countMap, 0);
        
        // At Most Two Distinct Characters
        int k = 2;
        
        for(int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            
            if(countMap[ch] == 0) distinct++;
            
            countMap[ch]++;
            
            if(distinct <= k) {
                result = Math.max(result, i-start+1);
            } else {
                while(distinct > k) {
                    ch = s.charAt(start++);
                    countMap[ch]--;
                    if(countMap[ch] == 0) {
                        distinct--;
                    }
                }
            }
        }
        
        return result;
    }
}

Follow up