You are given a binary string s.
You can perform the following operation on the string any number of times:
i from the string where i + 1 < s.length such that s[i] == '1' and s[i + 1] == '0'.s[i] to the right until it reaches the end of the string or another '1'. For example, for s = "010010", if we choose i = 1, the resulting string will be s = "000110".Return the maximum number of operations that you can perform.
Example 1:
Input: s = "1001101"
Output: 4
Explanation:
We can perform the following operations:
i = 0. The resulting string is s = "0011101".i = 4. The resulting string is s = "0011011".i = 3. The resulting string is s = "0010111".i = 2. The resulting string is s = "0001111".Example 2:
Input: s = "00111"
Output: 0
Constraints:
1 <= s.length <= 105s[i] is either '0' or '1'.In this approach, we will iterate through the string and count the number of operations we can perform. Each valid operation will involve swapping a pair of '10' to '01' by tracking the zeros followed by ones.
The function maximumOperations iterates through the string, counting the number of zeros we encounter. When a '1' follows the counted zeros, we can perform operations to push this '1' through all zero positions, incrementing our operations counter. This allows all '1's to continually shift through to the end.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), as we iterate through the string once.
Space Complexity: O(1), using constant extra space.
In this approach, we track the imbalance between '1's and '0's to calculate possible operations. The idea is to find how many '1's can become "stuck" behind '0's and count how many operations it would take to move each '1' to the end of the '0s'.
Here, the string is scanned to calculate an imbalance, which increases when a '1' is encountered and contributes to potential operations whenever a '0' follows. This approach tallies up by simulating moving '1's over '0's, counting each necessary move.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), going through the string once.
Space Complexity: O(1), no extra space beyond constant counters.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), as we iterate through the string once. |
| Scan and Balance Counting | Time Complexity: O(n), going through the string once. |
Stop solving 500+ Leetcode problems • Sahil & Sarra • 512,544 views views
Watch 9 more video solutions →Practice Maximum Number of Operations to Move Ones to the End with our built-in code editor and test cases.
Practice on FleetCode