2904. Shortest and Lexicographically Smallest Beautiful String

class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        int n = s.length();
        String result = "";
        int minLen = Integer.MAX_VALUE;

        int left = 0, ones = 0;
        for (int right = 0; right < n; right++) {
            if (s.charAt(right) == '1') {
                ones++;
            }

            // shrink from left while window has more than k ones,
            // or while shrinking still keeps exactly k ones
            while (ones > k || (left <= right && s.charAt(left) == '0' && ones == k)) {
                if (s.charAt(left) == '1') {
                    ones--;
                }
                left++;
            }

            if (ones == k) {
                int len = right - left + 1;
                String candidate = s.substring(left, right + 1);
                if (len < minLen || (len == minLen && candidate.compareTo(result) < 0)) {
                    minLen = len;
                    result = candidate;
                }
            }
        }

        return result;
    }
}

class Solution:
    def shortestBeautifulSubstring(self, s, k):
        n = len(s)
        result = ""
        min_len = float('inf')

        left = 0
        ones = 0

        for right in range(n):
            if s[right] == '1':
                ones += 1

            while ones > k or (
                left <= right and s[left] == '0' and ones == k
            ):
                if s[left] == '1':
                    ones -= 1
                left += 1

            if ones == k:
                candidate = s[left:right + 1]

                if (
                    len(candidate) < min_len or
                    (len(candidate) == min_len and candidate < result)
                ):
                    min_len = len(candidate)
                    result = candidate

        return result

class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        int n = s.length();
        string result = "";
        int minLen = INT_MAX;

        int left = 0;
        int ones = 0;

        for (int right = 0; right < n; right++) {
            if (s[right] == '1') {
                ones++;
            }

            while (
                ones > k ||
                (left <= right && s[left] == '0' && ones == k)
            ) {
                if (s[left] == '1') {
                    ones--;
                }
                left++;
            }

            if (ones == k) {
                string candidate = s.substr(left, right - left + 1);

                if (
                    candidate.length() < minLen ||
                    (candidate.length() == minLen &&
                     candidate < result)
                ) {
                    minLen = candidate.length();
                    result = candidate;
                }
            }
        }

        return result;
    }
};

class Solution {
    shortestBeautifulSubstring(s, k) {
        const n = s.length;
        let result = "";
        let minLen = Infinity;

        let left = 0;
        let ones = 0;

        for (let right = 0; right < n; right++) {
            if (s[right] === '1') {
                ones++;
            }

            while (
                ones > k ||
                (left <= right && s[left] === '0' && ones === k)
            ) {
                if (s[left] === '1') {
                    ones--;
                }
                left++;
            }

            if (ones === k) {
                const candidate = s.substring(left, right + 1);

                if (
                    candidate.length < minLen ||
                    (candidate.length === minLen && candidate < result)
                ) {
                    minLen = candidate.length;
                    result = candidate;
                }
            }
        }

        return result;
    }
}