1529. Minimum Suffix Flips

Time: O(n)

Space: O(1)

Approach

Greedily count each time the current state differs from target[i]; flip state on mismatch.

Key Techniques

String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.

Greedy

Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.

1529.cs

// Approach: Greedily count each time the current state differs from target[i]; flip state on mismatch.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinFlips(string target)
    {
        int ans = 0;
        int state = 0;

        foreach (char c in target)
        {
            if (c - '0' != state)
            {
                state = c - '0';
                ++ans;
            }
        }

        return ans;
    }
}

Was this solution helpful?