2904. Shortest and Lexicographically Smallest Beautiful String

String
Sliding Window
Greedy
Two Pointers

TIME

O(n^2)

SPACE

O(n)

Intuition

A beautiful substring can always be trimmed so it starts and ends on a 1: stripping leading or trailing zeros keeps the count of ones the same while shortening the string, which is strictly better for the primary objective. So every candidate worth considering is delimited by two ones.

That means only the positions of the ones matter. If ones lists those indices, then choosing k ones necessarily means choosing k consecutive entries ones[i .. i+k-1], and the tightest substring containing them runs from ones[i] to ones[i+k-1].

So there are only len(ones) - k + 1 candidates to compare, one per window of k ones.

Approach

Collect ones = indices where s[i] == '1'. If len(ones) < k, return "".
For each i in 0 .. len(ones) - k:
- The candidate spans [ones[i], ones[i + k - 1]], with length ones[i + k - 1] - ones[i] + 1.
- Track the best: shorter length wins; on equal length, the lexicographically smaller substring wins.
Return the best candidate.

Complexity

Time: O(n^2) worst case, O(n) windows, each substring extraction/comparison up to O(n)
Space: O(n), the ones list plus the current best substring

Edge Cases

Fewer than k ones in s → "" (Example 3)
k == 1 → the answer is "1" whenever any one exists
Equal-length candidates must be compared lexicographically, not just by position (Example 1 picks "11001" over other length-5 windows)
Candidates always begin and end with 1, so no trimming is needed afterward
All-ones string → answer is k ones

Code

class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        """
        2904. Shortest and Lexicographically Smallest Beautiful String
        Time: O(n^2)
        Space: O(n)
        """
        # A beautiful substring can always be trimmed to start and end on a '1',
        # so only windows of k consecutive ones matter.
        ones = [i for i, ch in enumerate(s) if ch == "1"]
        if len(ones) < k:
            return ""

        best = ""
        for i in range(len(ones) - k + 1):
            start, end = ones[i], ones[i + k - 1]
            candidate = s[start:end + 1]
            if not best or len(candidate) < len(best) or (
                len(candidate) == len(best) and candidate < best
            ):
                best = candidate
        return best

import java.util.ArrayList;
import java.util.List;

/**
 * 2904. Shortest and Lexicographically Smallest Beautiful String
 * Time: O(n^2)
 * Space: O(n)
 */
class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        // A beautiful substring can always be trimmed to start and end on a '1',
        // so only windows of k consecutive ones matter.
        List<Integer> ones = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                ones.add(i);
            }
        }
        if (ones.size() < k) {
            return "";
        }

        String best = "";
        for (int i = 0; i + k - 1 < ones.size(); i++) {
            int start = ones.get(i), end = ones.get(i + k - 1);
            String candidate = s.substring(start, end + 1);
            if (best.isEmpty()
                    || candidate.length() < best.length()
                    || (candidate.length() == best.length() && candidate.compareTo(best) < 0)) {
                best = candidate;
            }
        }
        return best;
    }
}