388. Shortest and Lexicographically Smallest Beautiful String

A shortest beautiful substring must begin and end with a '1' (any leading or trailing '0' can be trimmed while keeping exactly k ones and shrinking the length). So slide a window that carries at most k ones: strip leading zeros and drop surplus ones from the left, and whenever the window holds exactly k ones it is a candidate. Keep the best by length, breaking ties lexicographically.

Key observation

Any beautiful substring with a leading or trailing 0 can be shortened by dropping that 0 while still keeping exactly k ones. So every shortest beautiful substring starts and ends with 1. That means for each ending index that is a 1, there is exactly one shortest beautiful substring ending there — the one whose window contains precisely k ones with no wasted leading zeros.

Algorithm

Maintain a window [left, right] and a running count ones of 1s inside it.

1. Move right across s. When s[right] == '1', increment ones.
2. Normalize the left edge with a while loop: advance left whenever the window has too many ones (ones > k) or a leading zero (s[left] == '0'). Removing a '1' decrements ones; removing a '0' just shortens the window.
3. After normalizing, if ones == k the window is beautiful. Take cand = s[left..right] and update the answer if cand is shorter, or the same length but lexicographically smaller.

Worked example

s = "100011001", k = 3 (ones at indices 0, 4, 5, 8):

• right = 5: window has ones at 0, 4, 5 → ones = 3. Left edge is '1' at index 0, so candidate is "100011" (length 6). Best so far.
• right = 8: adding index 8 makes ones = 4 > 3. Drop the '1' at index 0 (ones = 3), then strip the zeros at 1, 2, 3. Window becomes indices [4, 8] = "11001" (length 5).
• "11001" (length 5) beats "100011" (length 6), so the answer is "11001".

Complexity

• Time: O(n) — each index enters and leaves the window at most once.
• Space: O(n) for the returned substring, O(1) auxiliary.

class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        String best = "";
        int left = 0, ones = 0;
        for (int right = 0; right < s.length(); right++) {
            if (s.charAt(right) == '1') ones++;
            // Normalize the left edge: drop surplus ones and strip leading zeros.
            while (left <= right && (ones > k || s.charAt(left) == '0')) {
                if (s.charAt(left) == '1') ones--;
                left++;
            }
            if (ones == k) {
                String cand = s.substring(left, right + 1);
                if (best.isEmpty() || cand.length() < best.length()
                        || (cand.length() == best.length() && cand.compareTo(best) < 0)) {
                    best = cand;
                }
            }
        }
        return best;
    }
}