A logically clear (yet rather slow in constant sense) java O(n) solution with comments


  • 0
    T
    public class Solution {
    
    public class countStruct{
        HashSet<Character> symbolTable;
        //positiveCount's keySet and vanitySymbol's are guaranteed to be complement (no intersection and union complete)
        //positiveCount is the redundant chars (can be 0)
        HashMap<Character,Integer> positiveCount;
        //vanityCount values > 0
        HashMap<Character,Integer> vanityCount;
        
        //O(length(C)), one time init, no worry
        public countStruct(char[] C){
        	this.symbolTable=new HashSet<Character>();
        	this.vanityCount=new HashMap<Character,Integer>();
        	this.positiveCount=new HashMap<Character,Integer>();
        	
            for (int i=0;i<C.length;i++){
            	this.symbolTable.add(C[i]);
            	if (vanityCount.keySet().contains(C[i])){
            		vanityCount.put(C[i],vanityCount.get(C[i])+1);
            	}
            	else {vanityCount.put(C[i],1);}
            }
        }
        
        //O(1)
        public void addElement(char c){
            //only process the char in symbolTable
            if (symbolTable.contains(c)){
                //if the symbol not yet exist in positiveCount
                if (vanityCount.keySet().contains(c)){
                    //remove from vanity table & add count 1 to positiveCount
                    vanityCount.put(c,vanityCount.get(c)-1);
                    if (vanityCount.get(c)==0){
                    	vanityCount.remove(c);
                    	positiveCount.put(c,0);
                    }
                }
                //if the symbol already exist in positiveCount
                else {
                    positiveCount.put(c,positiveCount.get(c)+1);
                }
            }
        }
        
        //O(1)
        public void removeElement(char c){
            //only process the char in symbolTable
            if (symbolTable.contains(c)){
            	//if is still in storage
                if (!vanityCount.keySet().contains(c)){
                    //decrease count
                    positiveCount.put(c,positiveCount.get(c)-1);
                    if (positiveCount.get(c)<0) {
                        positiveCount.remove(c);
                        vanityCount.put(c,1);
                    }
                }
                else {
                	vanityCount.put(c, vanityCount.get(c)+1);
                }
                
                
            }
        }
        
        //O(1), contain all necessary symbols iff vanitySymbol is empty
        public boolean satisfy(){
            return this.vanityCount.keySet().size()==0;
        }
        
        //debugging purpose
        public String toString(){
        	String output="";
        	output+="symbolTable:";
        	for (char c:this.symbolTable){output+=c+" ";}
        	output+="vanitySymbol:";
        	for (char c:this.vanityCount.keySet()){output+=c+"->"+this.vanityCount.get(c)+" ";}
        	output+="positiveCount:";
        	for (char c:this.positiveCount.keySet()){output+=c+"->"+this.positiveCount.get(c)+" ";}
        	
        	return output;
        }
        
    }
    
    public String minWindow(String s, String t) {
    	//true iff the minString is ever changed
    	boolean everAssigned=false;
    	
        char[] C1=s.toCharArray();
        char[] C2=t.toCharArray();
        int front=0;//index tobe added
        int back=0;//index tobe deleted
        String minString=s;
        //H is a HashMap that only cares the characters in T
        countStruct HC=new countStruct(C2);
        
        System.out.println(HC);//test
        while (front<C1.length){
            //if satisfys condition or not
            //if does: delete back and back++
            if (HC.satisfy()){
                HC.removeElement(C1[back]);
                back++;
            }
            //if not, add front and front++;
            else {
                HC.addElement(C1[front]);
                front++;
            }
            
            //finally, if the new string satisfy and is shorter or equal length
            if (HC.satisfy() && front-back<=minString.length()){
            	minString=s.substring(back,front);
            	everAssigned=true;
            }
        }
        while (HC.satisfy() && back<C1.length){
        	HC.removeElement(C1[back]);
            back++;
            if (HC.satisfy() && front-back<=minString.length()){
            	minString=s.substring(back,front);
            	everAssigned=true;
            }
        }
        //get the minString see if it truly satisfies the condition
        if (everAssigned){return minString;}
        else {return "";}
        
    }
    

    }


Log in to reply
 

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