Advertisement
whiletrue

Minimum Window Riddle

Dec 12th, 2012
1,566
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.07 KB | None | 0 0
  1. package riddles.strings;
  2.  
  3. import java.util.Arrays;
  4. import java.util.HashSet;
  5. import java.util.TreeMap;
  6. import java.util.TreeSet;
  7.  
  8. public class MinimumWindow {
  9.  
  10.     public static WindowObject getMinWin(char[] s, char[] c){
  11.  
  12.         WindowObject minWindow = null;
  13.  
  14.         /* Creating HashSet in order to query the chars in O(1) */
  15.         HashSet<Character> dic = new HashSet<Character>();
  16.         for(int i = 0; i < c.length; i++){
  17.             dic.add(c[i]);
  18.         }
  19.  
  20.         /* In order to keep track of "where I've seen it" */       
  21.         TreeMap<Character, Integer> where = new TreeMap<Character, Integer>();
  22.         /* In order to keep the indexes sorted */
  23.         TreeSet<Integer> indexInWindow = new TreeSet<Integer>();
  24.  
  25.         for(int i = 0; i < s.length; i++){
  26.             if(dic.contains(s[i])){
  27.                 /* If I've already seen this char */
  28.                 if(where.containsKey(s[i])){
  29.                     /* Remove its old index */
  30.                     indexInWindow.remove(where.get(s[i]));
  31.                 }
  32.                 /* Update/Insert its index */
  33.                 where.put(s[i], i);
  34.                 indexInWindow.add(i);
  35.  
  36.                 if(indexInWindow.size() == dic.size()){ /* I've seen all of them*/
  37.                     /* These are the window's edges */
  38.                     int firstIndex = indexInWindow.first();
  39.                     int lastIndex = indexInWindow.last();
  40.                     WindowObject currentWindow = new WindowObject(s, firstIndex, lastIndex);
  41.                     if(minWindow == null){ /* It's the first windows I see */
  42.                         minWindow = currentWindow;
  43.                     }else{
  44.                         if(minWindow.compareTo(currentWindow) > 0){
  45.                             /* If the minWindow bigger than what I just found */
  46.                             minWindow = currentWindow;
  47.                         }
  48.  
  49.                     }
  50.  
  51.                 }
  52.  
  53.             }
  54.         }
  55.  
  56.         return minWindow;
  57.     }
  58.  
  59.     public static void main(String args[]){
  60.         String s = "ADOBECODEBANC";
  61.         String c = "ABC";
  62.         WindowObject wo = MinimumWindow.getMinWin(s.toCharArray(), c.toCharArray());
  63.         if(wo == null){
  64.             System.out.println("Sorry! No windows were found!");
  65.         }else{
  66.             System.out.println("Found a Min Window with lenght: ["+wo.getWindow().length+"]");
  67.             System.out.println("Here it is: "+wo);
  68.         }
  69.     }
  70.  
  71.     static class WindowObject implements Comparable<WindowObject>{
  72.         private char[] window;
  73.         private int firstIndex, lastIndex;
  74.  
  75.         public WindowObject(char[] s, int firstIndex, int lastIndex){
  76.             this.window = Arrays.copyOfRange(s, firstIndex, lastIndex+1);
  77.             this.firstIndex = firstIndex;
  78.             this.lastIndex = lastIndex;
  79.         }
  80.  
  81.         public char[] getWindow(){
  82.             return this.window;
  83.         }
  84.  
  85.         @Override
  86.         public int compareTo(WindowObject w) {
  87.             if(this.window.length < w.getWindow().length){
  88.                 return -1;
  89.             }
  90.             if(this.window.length > w.getWindow().length){
  91.                 return 1;
  92.             }
  93.             return 0;
  94.         }
  95.  
  96.         @Override
  97.         public int hashCode(){
  98.             return this.window.hashCode();
  99.         }
  100.  
  101.         @Override
  102.         public boolean equals(Object o){
  103.             if(!(o instanceof WindowObject)){
  104.                 return false;
  105.             }
  106.             WindowObject w = (WindowObject) o;
  107.             return this.window.length == w.getWindow().length;
  108.         }
  109.  
  110.         @Override
  111.         public String toString(){
  112.             String s = "";
  113.             for(int i = 0; i < this.window.length; i++){
  114.                 s += this.window[i];
  115.             }
  116.             return s+" ["+this.firstIndex+"]["+this.lastIndex+"]";
  117.         }  
  118.  
  119.     }  
  120.  
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement