Java 4 ms two pointer no hashing solution (90%)


  • 1
    Z

    The idea is similar to all two pointers solution: starting from 0, move the end index until all required characters are included, and move the start index to exclude redundant characters.

    Instead of using map, I use two int arrays to store the characters' information. Note T is to store the number of characters in String t, and keeps unchanged. temp is the dynamic array we use for checking the characters in the substring. Every time a substring is found, check if it's the minimum length.

    public class Solution {
        public String minWindow(String s, String t) {
            int[] T = new int[128];
            int[] temp = new int[128];
    
            int st = 0,ed = 0,min_st = s.length(),min_ed = s.length(),t_size = t.length(),temp_size = 0;
            char[] ch = s.toCharArray();
            
            for(char c:t.toCharArray()){
                T[c]++;
            }
            
            while(ed<ch.length){
                //Expand window to contain all chars
                while(ed<ch.length&&temp_size<t_size){
                    //Update temp if it can be a candidate
                    if(T[ch[ed]]>0){
                        //candidate chosen
                        if(T[ch[ed]]>temp[ch[ed]]){
                            temp_size++;
                        }
                        temp[ch[ed]]++;
                    }
                    ed++;
                }
                //Shrink window to remove unused chars
                while(st<Math.min(ed,ch.length)&&(T[ch[st]]==0||T[ch[st]]<temp[ch[st]])){
                    //candidate removed
                    if(temp[ch[st]]>0){
                        temp[ch[st]]--;
                    }
                    st++;
                }
                //Shift window after a match
                if(temp_size==t_size){
                    if(min_ed==min_st||ed-st<min_ed-min_st){
                        min_st = st;
                        min_ed = ed;
                    }
                    temp[ch[st]]--;
                    st++;
                    temp_size--;
                }
            }
            return s.substring(min_st,min_ed);
        }
    }
    

Log in to reply
 

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