longest balance 0s and 1s string

xiaoningning · xiaoningning · commit 20d86868f6c4 · 2012-07-15T17:52:08.000-07:00
diff --git a/PuzzleCoding/src/LongestBalanceSubstring.java b/PuzzleCoding/src/LongestBalanceSubstring.java
@@ -0,0 +1,60 @@
+import java.util.HashMap;
+
+/**
+ Problem: Given a string which contains only 1 and 0,
+ find out its longest sub-string that contains equal number of �1� and �0�.
+ It should be done in O(n) time, O(n) space.
+
+ Example: �111100? => 1100, �00110? => 0110, �001111111000? => 111000.
+
+ We can use an array index to store the difference
+ between the number of 1s and the number of 0s up to each character in string S.
+ That is,we create an array diff with size equals to S.length + 1.
+ diff[i] is the number of �1�s appeared up to the ith character in S
+ subtracts the number of �0�s appeared up to ith character in S.
+
+ To be more specific, we have this counter initially set to 0,
+ if we meet a �1�, then counter increases by 1.
+ Otherwise the counter decreases by 1.
+ How long is the longest �1 and 0� balanced substring?
+ That is the longest distance between two identical counter in diff.
+ Because the counters are the same, they should meet same number of �1�s and �0�s in between.
+
+ */
+public class LongestBalanceSubstring {
+    public static void main(String[] args){
+        String s = "1001110010001";
+        String balanceString = longestBalanceSubstring(s);
+        System.out.println(balanceString);
+
+        String s1 = "0101001";
+        String balanceString1 = longestBalanceSubstring(s1);
+        System.out.println(balanceString1);
+
+    }
+    public static String longestBalanceSubstring(String s){
+        if(s.length() <=0)
+            return "";
+        int[] diffCounter = new int[s.length()+1];
+        diffCounter[0] = 0;
+        for(int i= 0; i < s.length(); i++){
+            diffCounter[i+1] = diffCounter[i] + ((s.charAt(i) == '0')? -1:1);
+        }
+        HashMap<Integer, Integer> counterIndex = new HashMap<Integer, Integer>();
+        for(int i = 1, j = diffCounter.length-1; i < j;){
+            if(!counterIndex.containsKey(diffCounter[i])){
+                counterIndex.put(diffCounter[i], i-1);
+                i++;
+            }else {
+                return s.substring(i,j);
+            }
+            if(!counterIndex.containsKey(diffCounter[j])){
+                counterIndex.put(diffCounter[j], j-1);
+                j--;
+            }else {
+                return s.substring(i-1,j);
+            }
+        }
+        return "";
+    }
+}
diff --git a/PuzzleCoding/src/ThreeSumClosest.java b/PuzzleCoding/src/ThreeSumClosest.java
@@ -93,7 +93,7 @@ public static int[] threeSumClosest(int[] a, int target) {
         return result;
     }
 
-    // non binary search
+    // non binary search O(n^3)
     public static int[] threeSumClosest1(int[] a, int target) {
         int[] result = new int[3];
 

Original file line number	Diff line number	Diff line change
`@@ -93,7 +93,7 @@ public static int[] threeSumClosest(int[] a, int target) {`
`93`	`93`	`return result;`
`94`	`94`	`}`
`95`	`95`
`96`		`- // non binary search`
	`96`	`+ // non binary search O(n^3)`
`97`	`97`	`public static int[] threeSumClosest1(int[] a, int target) {`
`98`	`98`	`int[] result = new int[3];`
`99`	`99`