Longest Ones After One Flip
Description
Given a binary array (containing only 0s and 1s), find the maximum length of contiguous 1s you can achieve by flipping at most one 0 to 1.
Example 1:
Input: s = [1, 0, 1, 1, 0]
Output: 4
Explanation: Flip the first 0 (index 1) to get [1, 1, 1, 1, 0]. Maximum contiguous 1s = 4.
Example 2:
Input: s = [1, 0, 1, 1, 0, 1]
Output: 4
Explanation: Flip index 1 to get [1, 1, 1, 1, 0, 1] with 4 contiguous 1s, OR flip index 4 to get [1, 0, 1, 1, 1, 1] with 4 contiguous 1s.
Example 3:
Input: s = [1, 1, 1, 1]
Output: 4
Explanation: All 1s already, no flip needed. Maximum = 4.
Example 4:
Input: s = [0, 0, 0]
Output: 1
Explanation: Flip any one 0 to get at most one contiguous 1.
Constraints
1 <= s.length <= 10^5s[i] is either 0 or 1
Complexity
Show Complexity
- Time:
O(n) - Space:
O(1)
Hints
Show Hints
- Pattern
- Use a sliding window that allows at most one 0
- Approach
- Expand right. If zeros > 1, shrink from left until zeros <= 1. Track max window size.
- Complexity
- Track the count of zeros in current window
Solutions
Show PY Solution
# we can only change 1 zero to one
def solution(s):
left = 0
count = 0
length = 0
for right in range(len(s)):
if s[right] == 0:
count += 1
while count > 1:
if s[left] == 0:
count -= 1
left += 1
length = max(length, right - left + 1)
return length