#2904

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Shortest and Lexicographically Smallest Beautiful String

Find the shortest beautiful substring in a binary string and return the lexicographically smallest option efficiently using a sliding window.

string sliding window

Problem Statement

You are given a binary string s and a positive integer k. A substring is called beautiful if it contains exactly k ones. Your task is to find the shortest beautiful substring and return the lexicographically smallest one among all candidates.

If no beautiful substring exists, return an empty string. The string length is at most 100, and k is guaranteed to be between 1 and the length of s. Optimize using a sliding window with running state updates to track the number of ones efficiently.

Examples

Example 1

Input: s = "100011001", k = 3

Output: "11001"

There are 7 beautiful substrings in this example:

The substring "100011001".
The substring "100011001".
The substring "100011001".
The substring "100011001".
The substring "100011001".
The substring "100011001".
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"

There are 3 beautiful substrings in this example:

The substring "1011".
The substring "1011".
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: ""

There are no beautiful substrings in this example.

Constraints

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

Solution Approach

Sliding Window Count

Use a sliding window to iterate through s, keeping track of the number of ones in the current window. Expand the right end until the count reaches k and then move the left end to shrink the window while maintaining exactly k ones.

Track Shortest Length

Whenever the window contains exactly k ones, compare its length with the current shortest length. If shorter, update the shortest length and record the substring. If equal, compare lexicographically to maintain the smallest substring.

Compare Lexicographically

After collecting candidate substrings of minimum length, select the one that is lexicographically smallest. This ensures both the shortest and smallest substring is returned efficiently using the running window state.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for the sliding window iteration over s, with constant time updates for counting ones. Space complexity is O(1) aside from storing the substring result since only counts and pointers are maintained.

What Interviewers Usually Probe

Looking for efficient substring tracking using a sliding window.
Check if candidate substrings maintain exactly k ones.
Expect consideration of lexicographical comparison during candidate updates.

Common Pitfalls or Variants

Common pitfalls

Forgetting to shrink the window after reaching k ones, leading to longer substrings.
Comparing substrings only by length and ignoring lexicographic order.
Incorrectly counting ones when the window moves, causing invalid candidates.

Follow-up variants

Find the longest beautiful substring instead of the shortest, keeping lexicographic minimization.
Change s to contain characters beyond binary and count a different target character.
Return all shortest beautiful substrings rather than a single lexicographically smallest one.

FAQ

What defines a beautiful substring in this problem?

A beautiful substring contains exactly k ones within the binary string s.

Why use a sliding window for Shortest and Lexicographically Smallest Beautiful String?

Sliding window allows efficient tracking of ones count without repeatedly scanning substrings, optimizing both length and lexicographic checks.

How do I ensure the substring is lexicographically smallest?

Compare candidate substrings of the same shortest length and select the one that comes first in dictionary order.

What if no beautiful substring exists?

Return an empty string if no substring contains exactly k ones.

What is the time complexity of this solution?

O(n) because each character is visited at most twice during the sliding window expansion and contraction.

terminal

Solution

Solution 1: Enumeration

We can enumerate all substrings $s[i: j]$, where $i \lt j$, and check if they are beautiful substrings. If so, we update the answer.

1

2

3

4

5

6

7

8

9

10

11

12

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

Solution 2: Two Pointers

We can also use two pointers to maintain a sliding window, where pointer $i$ points to the left boundary of the window, and pointer $j$ points to the right boundary of the window. Initially, $i$ and $j$ both point to $0$. In addition, we use a variable $cnt$ to record the number of $1$s in the sliding window.

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#2953 count complete substrings #2981 find longest special substring that occurs thrice i #2982 find longest special substring that occurs thrice ii