Shortest and Lexicographically Smallest Beautiful String Python/Java solution

Most implementations follow the same sliding window logic across languages. Python, Java, C++, C#, and JavaScript versions maintain two pointers, track the count of '1's, and update the best substring when the window contains exactly k ones. The algorithm remains O(n) regardless of language.

What is the best approach for Shortest and Lexicographically Smallest Beautiful String?

The sliding window approach is the most efficient and commonly used solution. It scans the string once while maintaining a window that tracks the number of '1's. When the window contains exactly k ones, it shrinks to produce the shortest valid substring and compares candidates lexicographically. This runs in O(n) time with O(1) extra space.

Is Shortest and Lexicographically Smallest Beautiful String asked at Google/Amazon/Meta?

Sliding window and substring optimization problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variants often ask for shortest or longest substrings satisfying character frequency constraints, making this pattern valuable for preparation.

What data structure is used in Shortest and Lexicographically Smallest Beautiful String?

The main technique uses a sliding window with two pointers and a simple counter for the number of '1's. Some implementations also use a prefix sum array to compute counts of '1's in constant time for any substring range.

What is the time complexity of Shortest and Lexicographically Smallest Beautiful String?

The optimal sliding window solution runs in O(n) time because each character is processed at most twice—once when the window expands and once when it shrinks. Space complexity is O(1) since only counters and pointers are stored. A prefix sum variant uses O(n) extra space.

Description Hints 2 Solution Video 6:46

2904. Shortest and Lexicographically Smallest Beautiful String

Q: Is Shortest and Lexicographically Smallest Beautiful String easy or hard?

This problem is generally classified as Medium difficulty. The challenge is recognizing the sliding window pattern and correctly handling both conditions: minimal substring length and lexicographical comparison when lengths tie.

Q: How to solve Shortest and Lexicographically Smallest Beautiful String in O(n)?

Use two pointers to maintain a sliding window and track the count of '1's inside the window. Expand the right pointer to include characters and increment the count when encountering '1'. When the window has more than k ones, move the left pointer until the constraint is restored. Whenever the window has exactly k ones, shrink it to the smallest valid size and compare it with the current best substring.

Medium59.8% acceptance2 companies

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

Asked at 2 companies

Wells Fargo Yelp

Topics

Sliding Window String

Hints open one at a time

Hint 1

Notice that if we consider that index i is the leftmost index of a beautiful substring, it has only one candidate j, such that s[i:j] is beautiful and shortest too.

Hint 2

We can iterate over all possibilities of leftmost index i take s[i:j] and compare with the shortest and the lexicographically smallest beautiful string we could get before index i.

6:46

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"100011001"
3

Input

"1011"
2

Input

"000"
1

Your code is saved on this device.Solution