A barely accepted solution, any advice??


  • 0
    R

    The idea is exactly the same as the one from Mike3.

    I used one map to store the frequency of character in String T.

    One queue to store the indices, another for the identity of character.

    The process is to iterate String S with the help of two queues. If duplicate character was found, both queue offer elements from the end.

    It took 644ms to pass. So any advice is appreciated.

    public class Solution {
    public String minWindow(String S, String T) {
        
        
        String result="";
        
        if (S.length()==0||T.length()==0) return result;
        
        if (S.length()<T.length()) return result;
        
        int count_left=T.length();
        
        Deque<Integer> index_queue= new LinkedList<Integer>();
        
        Deque<Character> character_queue = new LinkedList<Character>();
        
        Map<Character,Integer> count_map= new HashMap<Character,Integer>();
        
        for (int i=0;i<T.length();i++){
            char temp_char= T.charAt(i);
            
            if (count_map.containsKey(temp_char))
                count_map.put(temp_char,count_map.get(temp_char)+1);
                
            else count_map.put(temp_char,1);
        }
        
        for (int i =0;i<S.length();i++){
            char temp_char= S.charAt(i);
            
            if (count_map.containsKey(temp_char)){
                int count = count_map.get(temp_char);
                
                count_map.put(temp_char,count-1);
                character_queue.add(temp_char);
                index_queue.add(i);
                
                if (count>0)
                    count_left--;
                if (count_left==0&&result=="")
                    result=S.substring(index_queue.peek(),index_queue.peekLast()+1);
            }
            else continue;
    
            if (!character_queue.isEmpty()&&temp_char==character_queue.peek()){
                    while(count_map.get(character_queue.peek())<0){
            			char discard_char=character_queue.poll();
            			index_queue.poll();
            			count_map.put(discard_char,count_map.get(discard_char)+1);
            		}
                    String temp_result=S.substring(index_queue.peek(),index_queue.peekLast()+1);
                    if (temp_result.length()<result.length())
                    	result=temp_result;
            }                
        }
          return result;
    }
    

    }


Log in to reply
 

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