Problem 1529

Abstract / Summary

You must flip suffixes of a binary string to match a target, minimizing the number of flips needed.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1529.py

class Solution:
    def minFlips(self, target: str) -> int:
        result = 0
        use = 0
        for c in target:
            if int(c) != use:
                result += 1
                use    ^= 1

        return result
10 lines | 239 bytes | submitted January 4, 2024 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 74% (90k+ submissions).

Typical patterns to solve this problem:
  • Greedy
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation solves the problem of determining the minimum number of prefix-flip operations required to transform an initially all-zero binary string into a given target string. The algorithm proceeds in a single left-to-right pass, maintaining a logical “parity” that reflects whether the current position has been affected by an odd or even number of flips. Whenever the observed bit in the target differs from the expected bit under the current parity, a new flip is counted and the parity toggles. The final count represents the minimal sequence of flips needed.

Core Logic

Maintaining the Expected Bit

The variable use acts as a binary flag indicating the current parity of flips applied to the prefix ending at the current index. When use is 0, the expected bit at the current position matches the original all-zero state; when use is 1, the expected bit is the inverse of the original state. The comparison

if int(c) != use:

checks whether the target character c (converted to an integer) aligns with the expected bit under the current parity. If they differ, a flip is required at this position.

Counting a Flip and Updating Parity

When a mismatch is detected, the algorithm increments the result counter and toggles the parity flag:

result += 1
use ^= 1

The XOR assignment use ^= 1 flips the value of use between 0 and 1. This succinct operation captures the effect of applying a prefix flip: all subsequent positions will now be interpreted under the opposite parity.

Iterating Over the Target

The loop

for c in target:
    ...

processes each character of the target string exactly once, ensuring that the algorithm’s behavior is deterministic and directly tied to the input sequence.

Edge Cases Handled

The code gracefully handles an empty target string. In that scenario, the loop body never executes, leaving result at its initial value of 0, which correctly reflects that no flips are needed.

When the target consists entirely of '0' characters, the condition int(c) != use never becomes true because use remains 0 throughout the iteration. Consequently, result stays at 0, indicating that the initial all-zero state already matches the target.

Conversely, if the target is composed solely of '1' characters, the first character triggers a flip, toggling use to 1. From that point onward, each subsequent character matches the expected bit under the new parity, so only a single flip is counted. This demonstrates that the algorithm correctly identifies the minimal single-flip solution for a uniform '1' target.

Mixed patterns such as alternating '0101...' are also correctly processed. Each time the pattern changes relative to the current parity, the condition evaluates to true, prompting a flip and parity toggle. The algorithm therefore captures the exact number of transitions needed to align the evolving expected bit with the target sequence.

Performance Optimizations

The implementation achieves optimal runtime characteristics by avoiding any auxiliary data structures. All state is stored in two integer variables (result and use), which reside in registers for typical execution environments. The use of int(c) converts a single character to its numeric representation without constructing intermediate strings or lists.

The parity toggle employs the XOR-assignment operator (^=), which is a single machine instruction on most architectures, eliminating the need for conditional branching to flip the flag. This contributes to a tight inner loop that minimizes branch misprediction penalties.

Because the algorithm processes each character exactly once and performs only constant-time operations per iteration, it scales linearly with the length of the input string while maintaining a minimal memory footprint.

Complete Function

class Solution:
    def minFlips(self, target: str) -> int:
        result = 0
        use = 0
        for c in target:
            if int(c) != use:
                result += 1
                use ^= 1
        return result
written by openai gpt

ELI5 - Simplified Explanation

Imagine a long row of little light bulbs that are all turned off. A special machine wants to make these bulbs match a pattern that is written on a piece of paper. The paper shows a secret code of zeros and ones, where zero means the bulb should stay off and one means the bulb should turn on.

The code starts by looking at the first number in the pattern. If that number does not match how the light bulbs are currently acting, the machine flips the switch for all of the bulbs in that section. Every time the machine flips the switch, it counts that move. As it moves along the pattern, it keeps checking if the current state of the bulbs matches the next number in the code. If the numbers do not match, another flip is needed and the counter goes up again. By the time every number in the pattern has been checked, the final count shows how many times the switch had to be pulled to get everything exactly right.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.67 | σ = 1.49

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster Python C++ Java TS
WalkCCC C++ Java
leetcode.ca Python C++ Go Java Rust TS
Progiez Python C++ Java
github everthis JS
fartem Ruby
fsq C++
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
trung-hn Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Java
leetcode.ca C++, Go, Java, Python, Rust, TypeScript
Progiez C++, Java, Python
everthis JavaScript
fartem Ruby
fsq C++
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
trung-hn Python
23 links | 12 authors | 9 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

5 solutions   January 4, 2024

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality