# Shortest and Lexicographically Smallest Beautiful String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/shortest-and-lexicographically-smallest-beautiful-string)
Canonical: https://scaleengineer.com/dsa/problems/shortest-and-lexicographically-smallest-beautiful-string
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** String
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [Yelp](https://scaleengineer.com/companies/yelp), [Wells Fargo](https://scaleengineer.com/companies/wells-fargo)
---
## Problem
You are given a binary string `s` and a positive integer `k`.

A substring of `s` is **beautiful** if the number of `1`'s in it is exactly `k`.

Let `len` be the length of the **shortest** beautiful substring.

Return _the lexicographically **smallest** beautiful substring of string_ `s` _with length equal to_ `len`. If `s` doesn't contain a beautiful substring, return _an **empty** string_.

A string `a` is lexicographically **larger** than a string `b` (of the same length) if in the first position where `a` and `b` differ, `a` has a character strictly larger than the corresponding character in `b`.

* For example, `"abcd"` is lexicographically larger than `"abcc"` because the first position they differ is at the fourth character, and `d` is greater than `c`.

**Example 1:**

**Input:** s = "100011001", k = 3
**Output:** "11001"
**Explanation:** There are 7 beautiful substrings in this example:
1. The substring "100011001".
2. The substring "100011001".
3. The substring "100011001".
4. The substring "100011001".
5. The substring "100011001".
6. The substring "100011001".
7. The substring "100011001".
The length of the shortest beautiful substring is 5.
The lexicographically smallest beautiful substring with length 5 is the substring "11001".

**Example 2:**

**Input:** s = "1011", k = 2
**Output:** "11"
**Explanation:** There are 3 beautiful substrings in this example:
1. The substring "1011".
2. The substring "1011".
3. The substring "1011".
The length of the shortest beautiful substring is 2.
The lexicographically smallest beautiful substring with length 2 is the substring "11".

**Example 3:**

**Input:** s = "000", k = 1
**Output:** ""
**Explanation:** There are no beautiful substrings in this example.

**Constraints:**

* `1 <= s.length <= 100`
* `1 <= k <= s.length`

# Approaches
## Brute-Force Substring Enumeration
This approach involves generating every possible substring of the input string `s`, checking if it's "beautiful" (contains exactly `k` ones), and keeping track of the best one found so far based on the problem's criteria (shortest, then lexicographically smallest).
**Time:** O(N^3), where N is the length of the string `s`. There are O(N^2) substrings, and for each substring, counting the '1's takes up to O(N) time. · **Space:** O(N), where N is the length of the string `s`. This space is used to store the candidate substrings.
**Pros:** Simple to conceptualize and implement.
**Cons:** Highly inefficient due to three nested levels of iteration (or two loops with an O(N) operation inside).; Likely to result in a 'Time Limit Exceeded' (TLE) error for larger inputs.
### Explanation
The brute-force method is the most straightforward way to solve the problem. It systematically explores every single substring. The algorithm uses a pair of nested loops to define the start and end points of a substring. For each generated substring, it performs a check to see if it meets the 'beautiful' criteria by iterating through the substring and counting the '1's. If a substring is beautiful, it's compared against the best candidate found so far. A candidate is considered better if it's shorter, or if it's the same length but lexicographically smaller. This process continues until all O(N^2) substrings have been examined.

```java
class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        String result = "";
        int minLength = Integer.MAX_VALUE;

        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String sub = s.substring(i, j + 1);
                int onesCount = 0;
                for (char c : sub.toCharArray()) {
                    if (c == '1') {
                        onesCount++;
                    }
                }

                if (onesCount == k) {
                    if (sub.length() < minLength) {
                        minLength = sub.length();
                        result = sub;
                    } else if (sub.length() == minLength) {
                        if (sub.compareTo(result) < 0) {
                            result = sub;
                        }
                    }
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize `minLength` to a very large value and `result` to an empty string.
- Use two nested loops to generate all possible substrings. The outer loop `i` determines the start index, and the inner loop `j` determines the end index.
- For each substring `s.substring(i, j + 1)`, create a third loop to count the number of '1's within it.
- If the count of '1's equals `k`, the substring is 'beautiful'.
- Compare this beautiful substring with the current `result`.
  - If its length is less than `minLength`, update `minLength` and set `result` to this new substring.
  - If its length is equal to `minLength`, compare it lexicographically with the current `result` and update `result` if the new one is smaller.
- After checking all substrings, return the final `result`.

## Sliding Window
A more optimized solution uses the sliding window technique. This approach maintains a "window" (a substring) and expands/shrinks it to efficiently find all beautiful substrings without the redundant calculations of the brute-force method.
**Time:** O(N^2) in the worst case. Although each pointer moves at most N times, the substring creation and comparison inside the loop can take O(N) time, leading to a quadratic complexity. · **Space:** O(N) to store the result and candidate strings.
**Pros:** Significantly more efficient than the brute-force approach.; Avoids redundant counting of '1's for overlapping substrings.
**Cons:** The time complexity is still quadratic in the worst case due to repeated substring creation and comparison inside the loop.
### Explanation
The sliding window approach uses two pointers, `left` and `right`, to define the current substring under consideration. The `right` pointer always moves forward, expanding the window. We maintain a count of '1's within this window. When the count of '1's reaches `k`, we have found a beautiful substring. At this point, we can potentially shrink the window from the left. We check if the current window is the best solution so far. Then, we advance the `left` pointer. If the character leaving the window is a '1', we decrement our count. This allows us to efficiently transition from one beautiful substring to another.

```java
class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        String result = "";
        int minLength = Integer.MAX_VALUE;
        int left = 0;
        int onesCount = 0;

        for (int right = 0; right < s.length(); right++) {
            if (s.charAt(right) == '1') {
                onesCount++;
            }

            while (onesCount == k) {
                String candidate = s.substring(left, right + 1);
                if (candidate.length() < minLength) {
                    minLength = candidate.length();
                    result = candidate;
                } else if (candidate.length() == minLength) {
                    if (candidate.compareTo(result) < 0) {
                        result = candidate;
                    }
                }

                if (s.charAt(left) == '1') {
                    onesCount--;
                }
                left++;
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize `left` and `right` pointers to 0, `onesCount` to 0, `minLength` to a large value, and `result` to an empty string.
- Iterate through the string with the `right` pointer from left to right to expand the window.
- If `s.charAt(right)` is a '1', increment `onesCount`.
- Use a `while` loop that runs as long as `onesCount` is equal to `k`. This condition indicates the current window `[left, right]` is a beautiful substring.
  - Inside the `while` loop, get the current substring and compare it with the `result` to see if it's a better candidate (shorter or lexicographically smaller).
  - After checking, shrink the window from the left by incrementing the `left` pointer. If the character at the old `left` position was a '1', decrement `onesCount`.
  - The `while` loop continues to shrink the window as long as it remains beautiful, finding all beautiful substrings ending at the current `right`.
- After the main loop finishes, return the `result`.

## Pre-computation of '1's Indices
This is the most efficient approach, which builds upon a key insight: any shortest beautiful substring must necessarily start and end with a '1'. By pre-calculating the indices of all '1's, we can drastically reduce the number of substrings we need to check.
**Time:** O(N + M*N), where N is the string length and M is the number of '1's. O(N) for finding indices, and the loop runs M-k+1 times with O(N) work inside. In the worst case (M ≈ N), this is O(N^2), but it's practically much faster than the general sliding window if M is small. · **Space:** O(M), where M is the number of '1's in the string, to store the indices. In the worst case, this is O(N).
**Pros:** The most efficient approach by significantly pruning the search space.; Conceptually clean, as it directly targets the properties of the optimal solution.
**Cons:** Requires extra space to store the indices of all '1's.
### Explanation
This optimized method focuses only on the substrings that are viable candidates for being the shortest. A simple observation reveals that if a beautiful substring starts or ends with '0', we can always trim that '0' to get a shorter beautiful substring. Therefore, the shortest beautiful substring must start and end with '1'.

Based on this, the algorithm first scans the string to collect the indices of all '1's. Then, it slides a window of size `k` over this list of indices. Each window of `k` indices defines a minimal beautiful substring—one that starts with the first '1' in the window and ends with the last '1'. We compare all such minimal substrings to find the one that is shortest and lexicographically smallest.

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

class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        List<Integer> oneIndices = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                oneIndices.add(i);
            }
        }

        if (oneIndices.size() < k) {
            return "";
        }

        String result = "";
        int minLength = Integer.MAX_VALUE;

        for (int i = 0; i <= oneIndices.size() - k; i++) {
            int start = oneIndices.get(i);
            int end = oneIndices.get(i + k - 1);
            int len = end - start + 1;

            if (len < minLength) {
                minLength = len;
                result = s.substring(start, end + 1);
            } else if (len == minLength) {
                String candidate = s.substring(start, end + 1);
                if (candidate.compareTo(result) < 0) {
                    result = candidate;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- First, iterate through the string `s` to find and store the indices of all '1's in a list, let's call it `oneIndices`.
- If the size of `oneIndices` is less than `k`, it's impossible to form a beautiful substring, so return an empty string.
- Initialize `minLength` to a large value and `result` to an empty string.
- Iterate through the `oneIndices` list from `i = 0` to `oneIndices.size() - k`.
- For each `i`, the `i`-th '1' and the `(i + k - 1)`-th '1' form the boundaries of a minimal beautiful substring. The start index in `s` is `oneIndices.get(i)` and the end index is `oneIndices.get(i + k - 1)`.
- Calculate the length of this candidate substring.
- Compare its length and lexicographical order with the current `result` and update if it's a better candidate.
- After checking all `m-k+1` such minimal substrings, return the final `result`.

# Solutions
### Java

```java
class Solution {
public
  String shortestBeautifulSubstring(String s, int k) {
    int n = s.length();
    String ans = "";
    for (int i = 0; i < n; ++i) {
      for (int j = i + k; j <= n; ++j) {
        String t = s.substring(i, j);
        int cnt = 0;
        for (char c : t.toCharArray()) {
          cnt += c - '0';
        }
        if (cnt == k && ("".equals(ans) || j - i < ans.length() ||
                         (j - i == ans.length() && t.compareTo(ans) < 0))) {
          ans = t;
        }
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str: n = len(s) ans = "" for i in range(n): for j in range(i + k, n + 1): t = s[i: j] if t . count("1") == k and (not ans or j - i < len(ans) or (j - i == len(ans) and t < ans)): ans = t return ans

```

### CPP

```cpp
class Solution {
public:
  string shortestBeautifulSubstring(string s, int k) {
    int n = s.size();
    string ans = "";
    for (int i = 0; i < n; ++i) {
      for (int j = i + k; j <= n; ++j) {
        string t = s.substr(i, j - i);
        int cnt = count(t.begin(), t.end(), '1');
        if (cnt == k && (ans == "" || j - i < ans.size() ||
                         (j - i == ans.size() && t < ans))) {
          ans = t;
        }
      }
    }
    return ans;
  }
};

```