Leetcode 159) Longest Substring with At Most Two Distinct Characters

02 Nov 2021 in Algorithms

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

My Answer

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        //substring problem => sliding window technique
        int left =0; int right=0; int max=0;

        //I will map to keep up with values
        Map<Character, Integer> m = new HashMap<>();

        //iterate all the characters in s,
        while(right<s.length()){
            //add right to the window
            char curChar = s.charAt(right);
            if(m.containsKey(curChar)){
                m.put(curChar,m.get(curChar)+1);
            }else{
                m.put(curChar,1);
            }

            //trimming left
            while(m.size()>2){
                m.put(s.charAt(left),m.get(s.charAt(left))-1);
                if(m.get(s.charAt(left))==0){
                    m.remove(s.charAt(left));
                }
                left++;
            }

            //after that while loop, substring only contains at most 2 character type,
            if(max<right-left+1){
                max=right-left+1;
            }
            right++;
        }

        return max;


    }
}

Other Answer

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int start = 0, end = 0, counter = 0;
        int map[] = new int[128];
        int max = Integer.MIN_VALUE;
        while(end < s.length()) {
            char s1 = s.charAt(end);
            if(map[s1]==0) counter++;
            map[s1]++;

            while(start<end && counter>2) {
                char s2 = s.charAt(start);
                map[s2]--;
                if(map[s2]==0) counter--;
                start++;
            }
            max = Math.max(max,end-start+1);
            end++;
        }

        return max;
    }
}