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 ith step.
A binary string is prefix-aligned if, after the ith 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.
Example 1:
Input: flips = [3,2,4,1,5] Output: 2 Explanation: The binary string is initially "00000". After applying step 1: The string becomes "00100", which is not prefix-aligned. After applying step 2: The string becomes "01100", which is not prefix-aligned. After applying step 3: The string becomes "01110", which is not prefix-aligned. After applying step 4: The string becomes "11110", which is prefix-aligned. After applying step 5: The string becomes "11111", which is prefix-aligned. We can see that the string was prefix-aligned 2 times, so we return 2.
Example 2:
Input: flips = [4,1,2,3] Output: 1 Explanation: The binary string is initially "0000". After applying step 1: The string becomes "0001", which is not prefix-aligned. After applying step 2: The string becomes "1001", which is not prefix-aligned. After applying step 3: The string becomes "1101", which is not prefix-aligned. After applying step 4: The string becomes "1111", which is prefix-aligned. We can see that the string was prefix-aligned 1 time, so we return 1.
Constraints:
n == flips.length1 <= n <= 5 * 104flips is a permutation of the integers in the range [1, n].In this approach, we keep track of the highest index that has been flipped to '1'. At each step, if the highest flipped index equals the current step number (i.e., all indices up to and including the current step are '1'), we increment a counter for the number of times the string is prefix-aligned.
This C solution iterates over the flip indices, updating the maxFlippedIndex with the highest index seen so far. If the maxFlippedIndex equals the current (1-indexed) step number, it means the string is prefix-aligned at this step, so we increment the count.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(1)
This approach involves using a set to store the indices that have been flipped to '1'. We keep checking from the beginning if all indices up to the current step have been flipped, indicating a prefix alignment.
This Python solution utilizes a set to track flipped indices. After each flip, it checks if all numbers from 1 to current step (i + 1) are included in the set. If true, it increases the count, signifying a prefix alignment.
JavaScript
Time Complexity: O(n^2), Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Track Highest Flipped Index | Time Complexity: O(n), Space Complexity: O(1) |
| Use a Set to Track Flipped Indices | Time Complexity: O(n^2), Space Complexity: O(n) |
Interleaving Strings - Dynamic Programming - Leetcode 97 - Python • NeetCode • 112,299 views views
Watch 9 more video solutions →Practice Number of Times Binary String Is Prefix-Aligned with our built-in code editor and test cases.
Practice on FleetCode