TLE problem for my slide window code?


  • 0
    H

    I am a java beginner. can anybody help me check what is wrong with my code?
    I just use the slide window method and got TLE with the very long input strings case. I run lots of short cases and my code works well locally. For the long one how can I input it in? seems there is a limitation number of character in each script, right?

        public String minWindow(String S, String T) {
        int start = 0;                        // left edge of sliding window
        int end = 0;                         // right edge of sliding window
        int checkpoint = 0;              // record the starting point of minimum substring 
        int minlength = 0;                // record the length of the minimum substring
        if (S.length() < T.length()) return "";
    
        // initiate the sliding window
        for(int i = 1; i < S.length(); i++){                              
            if (compareString(S.substring(0,i),T) == 1){ 
                end = i;
                break;
            }
        } 
        if (end == 0) return "";	 // didn't find window
        minlength = end;        
               
        while(end <= S.length()){                                        // start sliding 
    
           // move left edge of window till S.substring < T and record the minimum length and checkpoint
            while(compareString(S.substring(start,end),T) == 1) {     
                if (minlength > (end-start)){ 
                    checkpoint = start;
                    minlength = end-start;
                }
    			start++; 
            }
    
            // move right edge of window till S.substring =T
            while(compareString(S.substring(start,end),T) == -1){
                end++;
    			if (end > S.length()) break;
            }
        }
        return S.substring(checkpoint, checkpoint+minlength);
    }
    
        
    private int compareString(String a, String b){   
    

    // a is substring of S and b is T, a contains b 1, else -1
    // convert a and b to HashMap, if any element in B is not in A or its value in B larger than in A return -1
    HashMap<Character, Integer> A = new HashMap<Character, Integer>();
    HashMap<Character, Integer> B = new HashMap<Character, Integer>();

        for(int i = 0; i < a.length(); i ++){
            if (!A.containsKey(a.charAt(i))) A.put(a.charAt(i), 1);
            else A.put(a.charAt(i) , A.get(a.charAt(i))+1);
        }
        for(int i = 0; i < b.length(); i ++){
            if (!B.containsKey(b.charAt(i))) B.put(b.charAt(i), 1);
            else B.put(b.charAt(i), B.get(b.charAt(i))+1);
        }
        for(char cha: B.keySet()){
            if(!A.containsKey(cha) || A.get(cha)<B.get(cha)) return -1;
        }
        return 1;
    }

Log in to reply
 

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