Easy Understand AC Solution Without HashMap


  • 1

    Use array and a variable count instead of HashMap, which makes it a little faster. By the way, it is also acceptable to K Distinct Character, we just need to change count > 2 to count > k. Really easy, right?

    public class Solution {
        public int lengthOfLongestSubstringTwoDistinct(String s) {
            int[] cnt = new int[256];// record the emerge times for this substring
            int begin = 0, end = 0, distance = Integer.MIN_VALUE, count = 0;
            while(end < s.length()){
                if(cnt[s.charAt(end++)]++ == 0)     count++;
                while(count > 2){
                    if(--cnt[s.charAt(begin++)] == 0)   count--;
                }
                distance = Math.max(distance, end - begin);
            }
            return distance == Integer.MIN_VALUE? 0 : distance;
        }
    }
    

  • 0

    The idea is easy to understand, but the code is really hard to read... I have pasted a more readable version according to your code...

        public int lengthOfLongestSubstringTwoDistinct(String s) {
            int[] cnt = new int[256];
            int begin = 0, end = 0, distance = Integer.MIN_VALUE, count = 0;
            
            while(end < s.length())
            {
                if(cnt[s.charAt(end)] == 0) // a new character
                {
                    count++;
                }
                
                cnt[s.charAt(end)]++; // increase the count
                end++; //move the end pointer
                
                while(count > 2) // if more than 2 distinct characters
                {
                    cnt[s.charAt(begin)]--; // decrease the count
                    if(cnt[s.charAt(begin)] == 0) // if the character is not in the substring anymore
                    {
                      count--;  
                    }
                    begin++; // move the begin pointer
                }
                distance = Math.max(distance, end - begin); // update the length
            }
            return distance == Integer.MIN_VALUE? 0 : distance;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.