Algorithm

The brute force approach is to traverse the given string n-k times and for every index, traverse the nested loop for k times and check whether the given part of the string contains at least one. If it is, this means no flips are required. Otherwise, the flip is required.

For every index, if we need to flip a bit, then we will flip the last most bit of that substring so that this bit can be used for other substrings also.

Code

#include <bits/stdc++.h>
using namespace std;

// Solution class to find minimum flips so every substring of length k has at least one '1'
class Solution {
public:
    // Function to calculate minimum flips (brute force approach)
    int minFlips(string s, int k) {
        int flips = 0;
        vector<char> arr(s.begin(), s.end());
        int n = arr.size();

        // Iterate over all substrings of length k
        for (int i = 0; i <= n - k; i++) {
            bool hasOne = false;
            // Check if substring has at least one '1'
            for (int j = i; j < i + k; j++) {
                if (arr[j] == '1') {
                    hasOne = true;
                    break;
                }
            }

            // If no '1', flip the last bit of substring to '1'
            if (!hasOne) {
                if (arr[i + k - 1] == '0') {
                    arr[i + k - 1] = '1';
                    flips++;
                }
            }
        }
        return flips;
    }
};

int m