Untitled

#include <iostream>
#include <string>
using namespace std;

string getSubstring(string input_str, int k) {
    int n = input_str.size();
    int count = 0;
    int start = 0;
    string result = ""; 
    
    for (int i = 0; i < n; i++) {
        // Count the number of '1's in the window
        if (input_str[i] == '1') count++;
        
        // Once we have exactly k '1's, try to find the smallest valid substring
        if (count == k) {
            // Move the start pointer to minimize the window
            while (input_str[start] == '0') start++;
            
            string candidate = input_str.substr(start, i - start + 1);
            
            // Compare lexicographically and check for smallest length
            if (result == "" || candidate.size() < result.size() || 
                (candidate.size() == result.size() && candidate < result)) {
                result = candidate;
            }
            
            // Move start to find the next valid window by removing the leftmost '1'
            if (input_str[start] == '1') count--;
            start++;
        }
    }
    
    return result;
}

int main() {
    string input_str = "110011101";
    int k = 4;
    cout << getSubstring(input_str, k) << endl;
    return 0;
}