Each substring of a certian length of a binary substring should have at least one '1' character

You have been given a binary string containing only the characters '1' and '0'.

Calculate how many characters of the string need to be changed in order to make the binary string such that each of its substrings of at least a certain length contains at least one "1" character.

I came to think of the following idea but it fails for many testcases:

public static int minimumMoves(String s, int d) {
        int n = s.length();
        
        int i=0, answer = 0;
        while(i<n)
        {
            boolean hasOne = false;
            int j=i;
            while(j<n && j<i+d)
            {
                if(s.charAt(j) == '1') 
                {
                    hasOne = true;
                    break;
                }
                j++;
            }
            if(!hasOne) {
                answer++;
                i += d;
            }
            else i++;
        }
        return answer;
}

Also my algorithm runs on O(|s|²) time. Can anyone suggest ideas on O(|s|) time?

Just throwing off an idea:

return s.split("(?<=\\G.{" + String.valueof(d) + "})").stream().filter(str -> str.contains("1")).count()

I used the sliding window technique and Deque to solve this. This is my accepted solution:

public static int minimumMoves(String s, int d) {
    int n = s.length();
    Deque<Character> dq = new LinkedList<>();
    int count = 0, answer = 0;
    
    for(int i=0; i<d; i++)
    {
        if(s.charAt(i) == '1') count++;
        dq.addLast(s.charAt(i));
    }
    
    if(count == 0) {
        answer++;
        count++;
        dq.removeLast();
        dq.addLast('1');
    }
    
    int i=d;
    
    while(i<n)
    {
        if(dq.getFirst() == '1') count--;
        dq.removeFirst();
        
        if(s.charAt(i) == '1') count++;
        dq.addLast(s.charAt(i));
        
        if(count == 0)
        {
            answer++;
            dq.removeLast();
            dq.addLast('1');
            count++;
        }
        i++;
    }
    
    return answer;
    
}

You just need to use a sliding window and a count of 1s so far at each index. Use a sliding window of d and if you don't see any ones so far, update the last index of that window with 1 and increment the result.

Code below:

public static int minimumMoves(String s, int d) {
int n = s.length();
int[] count = new int[n+1];
int res = 0;
for ( int i = 1; i <= d; i++ ) {
if ( s.charAt(i-1) == '1') count[i] = count[i-1]+1;
else count[i] = count[i-1];
}
if ( count[d] == 0 ) {
res++;
count[d] = 1;
}
for ( int i = d+1; i <= n; i++ ) {
if ( s.charAt(i-1) == '0' ) {
count[i] = count[i-1];
int ones = count[i] - count[i-d];
if ( ones == 0 ) {
count[i] = count[i-1] + 1;
res++;
}
} else {
count[i] = count[i-1] + 1;
}
}
return res;
}

You just need to break ensure there is no run of d zeros.

public static int minimumMoves(String s, int d) {
int result = 0;
int runLength = 0;
for(char c: s.toCharArray()) {
if (c == '0') {
runLength += 1;
if (runLength == d) { // we need to break this run
result += 1;
runLength = 0;
}
} else {
runLength = 0;
}
}
return result;
}

Thought of another implementation you can do for this by working from the maximum possible changes (assumes at start that all values are '0' in String), reduce it when it finds a '1' value, and then jump to the next substring start. This allows it to run in O(n) and Ω(n/m) (n = String length, m = Substring length).

  public static int minimumMoves(String s, int d)
{
char[] a = s.toCharArray();
//Total possible changes (not counting tail)
if(a.length < d)
return 0;
int t = (int) a.length / d;
//Total possible changes (counting tail)
//int t = (int) Math.ceil((double) a.length / (double) d);
for(int i = 0; i < a.length; i++)
{
if(a[i] == '1')
{
t--;
//Calculate index for start of next substring
i = (i / d + 1) * d - 1;
}
}
return t;
}