1758. Minimum Changes To Make Alternating Binary String

UnknownView on LeetCode

String Greedy

Time: O(n)

Space: O(1)

Intuition

Minimum operations to make string alternating. Count 010101... vs 101010... patterns and take minimum.

Algorithm

1Count mismatches with "010101..." pattern = c1. Mismatches with "101010..." = n - c1.
2Return min(c1, n-c1).

Common Pitfalls

•Only two valid alternating patterns for binary strings. Count mismatches with each.

1758.cs

// Approach: Count mismatches for '1010...' pattern; answer is min(cost, n-cost).
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinOperations(string s)
    {
        int cost10 = 0; // the cost to make s "1010"

        for (int i = 0; i < s.Length; ++i)
        {
            if ((s[i] - '0') == i % 2)
                ++cost10;
        }

        int cost01 = s.Length - cost10; // the cost to make s "0101"
        return Math.Min(cost10, cost01);
    }
}

Was this solution helpful?