# Longest Subarray with Ones after Replacement (Max Consecutive Ones after replacement)

AlgorithmsAugust 02, 20211 mins read## Problem Statement

Given an array A of `0's`

and `1's`

, and a value K which indicates that you may change up to K values from 0 to 1. Return the length of the longest (contiguous) subarray that contains only 1’s.

**Example 1:**

```
Input: A = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], K = 2
Output: 6
To obtain the longest contiguous subarray of 1s, you can flip the 0s at index 5 and 10 to 1s:
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
```

**Example 2:**

```
Input: A = [0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], k=3
Output: 9
Explanation: Replace the 0s at index 6, 9, and 10 with 1s to get the longest contiguous subarray of 1s.
```

## Solution in Java

This problem is a variation of the problem Longest Substring with Same Letters after Replacement. We can solve it using a similar **sliding window strategy** discussed in the previous problem.

This problem can be solved using the sliding window pattern.

- Initialize two variables:
`windowStart = 0`

and`windowEnd = 0`

. These define the lower and upper bounds of the sliding window. So we start with an initial window size of`1`

. - Initialize a variable
`numReplacements`

to keep track of the number of replacements done from`0`

to`1`

. - Iterate over the array until the
`windowEnd`

index reaches the end of the array.- If
`a[windowEnd] == 0`

, then we need to flip this element to`1`

to obtain a contiguous subarray of 1s. Therefore, we increment`numReplacements`

. - If
`numReplacements`

is greater than the number of allowed replacements, then we can’t proceed, and we must shift our window by incrementing`windowStart`

until`numReplacements`

becomes equal to the number of allowed replacements. - In every iteration, we check if the current length of longest contiguous subarray of 1s is greater than the previous value, and we set the longest length accordingly.

- If

```
import java.util.Scanner;
class LongestSubarrayWithOnesAfterReplacement {
private static int findMaxConsecutiveOnes(int[] a, int k) {
int maxOnes = Integer.MIN_VALUE;
int numReplacements = 0;
int windowStart = 0;
for(int windowEnd = 0; windowEnd < a.length; windowEnd++) {
if(a[windowEnd] == 0) {
numReplacements++;
}
while(numReplacements > k) {
if(a[windowStart] == 0) {
numReplacements--;
}
windowStart++;
}
maxOnes = Math.max(maxOnes, windowEnd-windowStart+1);
}
return maxOnes;
}
public static void main(String[] args) {
int[] a = new int[]{1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
int k = 2;
int result = findMaxConsecutiveOnes(a, k);
System.out.printf("Length of longest contiguous subarray containing only 1s after replacement = %d%n", result);
}
}
```

```
# Output
Length of longest contiguous subarray containing only 1s after replacement = 6
```