educative.io

Educative

Easier solution logic

Instead of keeping track of maxOnesCount, I found it easier to keep track of both counts. I thought the code was a lot more simple:

def length_of_longest_substring(arr, k):
    start, max_len = 0, 0
    freq = {0: 0, 1: 0}

    for end in range(len(arr)):
        freq[arr[end]] += 1
        while (freq[0] > k):
            freq[arr[start]] -= 1
            start += 1
        max_len = max(max_len, end-start+1)

    return max_len
2 Likes

I find it easier to just keep track of zeros. So use max_zero_count instead.

3 Likes

yes, thats correct, you don’t need to keep track of ones either, just count number of zeros so no dict either.

The Solution Description for this one is a disservice, overly complex.
It sent me down a lengthy rabbit hole.

This is the simplest solution I can find. Thanks go to Lee215 on Leetcode (Java, C++, Python).

Uses a minimum of variables.
Does not bother to track num zeroes (mutate K instead).
Allows K to be negative.

var longestOnes = function(A, K) {
  let L = 0;
  let R = 0;
  while(R < A.length) {
    if(A[R] === 0) K--;
    if(K < 0 && A[L++] === 0) K++;
    R++;
  }
  return R - L;
};
2 Likes

Yes. That’s what I was wondering too! counting zeroes is easy. Here is my solution:

public int findLength(int[] digits, int k) {
        int maxLength = 0;
        int start = 0;
        int zeroCount = 0;
        for (int end = 0; end < digits.length; end++) {
            if (digits[end] == 0) {
                zeroCount++;
            }
            if (zeroCount > k) {
                if (digits[start] == 0) {
                    zeroCount--;
                }
                start++;
            }
            maxLength = Integer.max(maxLength, end - start + 1);
        }
        return maxLength;
    }