Minimum Number of Swaps to Make the Binary String Alternating

This approach optimizes the counting method by gathering all necessary information—total counts of '0's and '1's, and the number of misplaced characters for both potential alternating patterns—in a single pass through the input string. This avoids redundant iterations and makes the implementation more compact and efficient.

1. Initialize counters: ones = 0, misplaced_for_0_start = 0, and misplaced_for_1_start = 0.
2. Iterate through the string s with index i from 0 to n-1 in a single pass.
3. Inside the loop:
   • Increment ones if s[i] is '1'.
   • Check the character at the current index i against the two possible alternating patterns.
   • If i is an even position:
     • If s[i] is '1', it's a misplaced character for a target starting with '0'. Increment misplaced_for_0_start.
     • If s[i] is '0', it's a misplaced character for a target starting with '1'. Increment misplaced_for_1_start.
4. After the loop, calculate zeros = n - ones.
5. Check for impossibility: if abs(ones - zeros) > 1, return -1.
6. Determine the result based on n's parity:
   • If n is even, return min(misplaced_for_0_start, misplaced_for_1_start).
   • If n is odd:
     • If ones > zeros, the target must start with '1'. Return misplaced_for_1_start.
     • Else, the target must start with '0'. Return misplaced_for_0_start.

Instead of making separate passes, we can count everything at once. We iterate through the string a single time, keeping track of the total number of '1's, as well as the number of swaps needed for both the '0'-starting and '1'-starting alternating patterns.

The number of swaps for a target starting with '0' (0101...) is the number of '1's at even positions. The number of swaps for a target starting with '1' (1010...) is the number of '0's at even positions. We can count both of these during our single traversal.

After the loop, we have all the necessary counts. We first check if a solution is possible using the total counts of '0's and '1's. If it is, we use the pre-calculated swap counts to return the answer based on the string's length, just as in the previous approach.

class Solution {
    public int minSwaps(String s) {
        int n = s.length();
        int ones = 0;
        int misplaced_for_0_start = 0; // Counts '1's at even positions
        int misplaced_for_1_start = 0; // Counts '0's at even positions

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '1') {
                ones++;
            }
            if (i % 2 == 0) { // Check characters at even positions
                if (c == '1') {
                    misplaced_for_0_start++;
                } else { // c == '0'
                    misplaced_for_1_start++;
                }
            }
        }

        int zeros = n - ones;
        if (Math.abs(ones - zeros) > 1) {
            return -1;
        }

        if (n % 2 == 0) {
            // For even length, both targets are possible.
            // The number of misplaced '1's at even positions must equal misplaced '0's at even positions for the two targets.
            return Math.min(misplaced_for_0_start, misplaced_for_1_start);
        } else {
            // For odd length, only one target is possible.
            if (ones > zeros) { // Target must start with '1'
                return misplaced_for_1_start;
            } else { // Target must start with '0'
                return misplaced_for_0_start;
            }
        }
    }
}