Subsequence Hate

charles-wangkai · charles-wangkai · commit 6844c31d519a · 2020-06-03T12:16:17.000+08:00
diff --git a/1363/B/Main.java b/1363/B/Main.java
@@ -0,0 +1,31 @@
+import java.util.Scanner;
+
+public class Main {
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+
+        int t = sc.nextInt();
+        for (int tc = 0; tc < t; ++tc) {
+            String s = sc.next();
+
+            System.out.println(solve(s));
+        }
+
+        sc.close();
+    }
+
+    static int solve(String s) {
+        int[] lefts = new int[2];
+        int[] rights = new int[] { s.replaceAll("1", "").length(), s.replaceAll("0", "").length() };
+        int result = Math.min(rights[0], rights[1]);
+        for (char ch : s.toCharArray()) {
+            int digit = ch - '0';
+            ++lefts[digit];
+            --rights[digit];
+
+            result = Math.min(result, Math.min(lefts[0], lefts[1]) + Math.min(rights[0], rights[1]));
+        }
+
+        return result;
+    }
+}
