My O(N) Accepted Java Solution


  • 0
    public class Solution {
        
        private static final int SUB=32;
        private static final int FINAL_SIZE=128;
        public String minWindow(String s, String t) {
            
            if(s==null||t==null||s.length()==0||t.length()==0)
        {
            return "";
        }
        
        int[] charData=getCharData(t);
        int[] sCounts=new int[Solution.FINAL_SIZE-Solution.SUB];
        int start=-1;
        int end=-1;
        
        int i=0;
        for(int j=0;j<s.length();j++)
        {
            int idx=(int)s.charAt(j)-Solution.SUB;
            sCounts[idx]++;
            
            while(i<=j && sCounts[((int)s.charAt(i)-Solution.SUB)]>charData[((int)s.charAt(i)-Solution.SUB)])
                {
                    sCounts[((int)s.charAt(i)-Solution.SUB)]--;
                    i++;
                }
            if(allCharsPresent(sCounts,charData))
            {
                if(end==-1||(((j-i)+1)<((end-start)+1)))
                {
                    start=i;
                    end=j;
                }
            }
            
        }
        
        return end==-1?"":s.substring(start,end+1);
            
        }
        
        private boolean allCharsPresent(int[] c, int[] b)
        {
            for(int i=0;i<b.length;i++)
            {
               
            
                if((b[i]>0) && (c[i]<b[i]))
                {
                    return false;
                }
            }
            return true;
        }
        
        private int[] getCharData(String t)
        {
            int[] b=new int[Solution.FINAL_SIZE-Solution.SUB];
            for(int i=0;i<t.length();i++)
            {
                int idx=(int)t.charAt(i)-Solution.SUB;
                b[idx]++;
            }
            return b;
        }
    }

Log in to reply
 

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