Problem Description
Given a binary string of length n (1-indexed) initially filled with 0’s, you will flip specific positions to 1’s following the order provided in the array flips. After each flip, the string is said to be prefix-aligned if all the bits from index 1 through i (where i is the number of flips performed so far) are 1’s and all subsequent bits are 0’s. The task is to determine how many times the binary string becomes prefix-aligned during the flipping process.
Key Insights
- The flip order is a permutation of [1, n], ensuring each index is flipped exactly once.
- A key observation is that the string is prefix-aligned at step i if and only if the maximum index flipped so far equals i.
- We can track the maximum index seen so far while iterating through flips and count the instances when this maximum index matches the current number of flips.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
We use a one-pass approach by iterating through each flip while keeping track of the maximum flipped index seen so far (maxFlipped). If at any step the maximum index equals the number of flips performed, it means that all indices from 1 to that step have been flipped, and the string is prefix-aligned. Thus, we increment our counter. This method only requires constant extra space and iterates through the list once.