Problem Description
You have a 1-indexed binary string of length n where all the bits are 0 initially. We will flip all the bits of this binary string (i.e., change them from 0 to 1) one by one. You are given a 1-indexed integer array flips where flips[i] indicates that the bit at index i will be flipped in the i-th step. A binary string is prefix-aligned if, after the i-th step, all the bits in the inclusive range [1, i] are ones and all the other bits are zeros. Return the number of times the binary string is prefix-aligned during the flipping process.
Key Insights
- The binary string starts as all zeros.
- Each flip changes a specific bit from 0 to 1.
- A prefix-aligned string means that all bits from the start up to the current index are 1s.
- We need to track the maximum index flipped so far and compare it to the current step index to determine if the string is prefix-aligned.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
To solve this problem, we can use a single pass through the flips array while maintaining two variables: max_flipped, which keeps track of the maximum index that has been flipped, and a counter for the number of times the string is prefix-aligned. During each step i, we update max_flipped with the current flip value and check if max_flipped is equal to i. If it is, we increment the prefix-aligned count. This approach ensures we only need to traverse the list once, resulting in an efficient solution.