Skip to main content
Talentd

Shortest and Lexicographically Smallest Beautiful String - Solution & Explanation

MediumStringSliding Window26 min readAsked at: Wells Fargo, Yelp
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given a binary string s and an integer k, you must find the shortest substring containing exactly k occurrences of '1'. If multiple substrings share the same minimal length, return the lexicographically smallest one. If no such substring exists, return an empty string.

Approach 1: Sliding Window Technique (O(n) time, O(1) space)

This approach uses the classic Sliding Window pattern. Maintain two pointers left and right and expand the window by moving right. Track how many '1' characters exist in the current window. When the count exceeds k, move left forward until the window becomes valid again. Every time the window contains exactly k ones, attempt to shrink it from the left while preserving the condition to ensure the substring is as short as possible.

Each valid window represents a candidate substring. Compare it with the current best result: prefer the shorter substring, and if lengths match, pick the lexicographically smaller one using standard string comparison. Since each character enters and leaves the window at most once, traversal is linear. Space usage remains O(1) because only counters and pointers are stored.

Approach 2: Prefix Sum and Two Pointers (O(n) time, O(n) space)

This method relies on prefix sums to quickly compute the number of '1' characters in any substring. Build a prefix array where prefix[i] stores the count of ones up to index i. With this structure, the number of ones in s[l..r] becomes prefix[r+1] - prefix[l]. Use a Two Pointers strategy to scan possible windows while checking the count using prefix lookups.

When a window contains exactly k ones, attempt to tighten the left boundary to minimize the substring length. Record candidate substrings and apply lexicographic comparison when lengths tie. Prefix sums make the count check constant time, avoiding repeated scans of the substring. This approach is helpful if you already rely on prefix arrays for multiple range queries in a larger system.

The core difficulty lies in balancing two goals: minimal length and lexicographical order. The sliding window approach naturally produces minimal windows while scanning left to right, which keeps comparisons manageable.

Recommended for interviews: The Sliding Window approach is the expected solution. It demonstrates strong understanding of window expansion, contraction, and maintaining constraints in linear time. Mentioning a prefix sum alternative shows deeper familiarity with string range-count techniques, but the sliding window version is typically cleaner and uses constant extra space.

Approach 1: Sliding Window Technique

The sliding window technique involves maintaining a window over the string that adjusts to include exactly k '1's, which constitutes a beautiful substring. We then aim to find the shortest such window, and among those, the lexicographically smallest substring.

This C implementation uses a sliding window (two pointers, l and r) to find the shortest segment of the string that contains exactly k '1's. It also keeps track of the lexicographically smallest substring that fits these criteria by comparing each new candidate with the smallest found so far.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string. This is because each character is processed at most twice (once by r and once by l).
Space Complexity: O(k) for storing the result substring.

Try this approach in the editor →

Approach 2: Prefix Sum and Two Pointers

This approach uses a prefix sum to keep track of the number of '1's up to each index and then applies a two-pointer technique to identify the shortest valid substring. The idea is to efficiently calculate the number of '1's in any segment by referencing the prefix sum array. Once a substring with exactly k '1's is found, it is compared against the current smallest lexicographical segment stored.

This C solution uses the prefix sum array to keep track of the number of '1's up to each position. The two pointers help identify the substring range with exactly k '1's and update the result if it's the smallest found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), for constructing prefix sum and traversing the string. Space Complexity: O(n) for the prefix sum array.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n^3), and the space complexity is O(n). Here, n is the length of the string s.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: 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 1s in the sliding window.

We first move pointer j to the right, add s[j] to the sliding window, and update cnt. If cnt is greater than k, or if i is less than j and s[i] is 0, we move pointer i to the right and update cnt.

When cnt equals k, we have found a beautiful substring. We compare it with the current answer and update the answer if necessary.

The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the string s.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Technique

Time Complexity: O(n), where n is the length of the string. This is because each character is processed at most twice (once by r and once by l).
Space Complexity: O(k) for storing the result substring.

Prefix Sum and Two Pointers

Time Complexity: O(n), for constructing prefix sum and traversing the string. Space Complexity: O(n) for the prefix sum array.

Enumeration—
Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window TechniqueO(n)O(1)Best general solution for scanning substrings with constraints like exactly k ones
Prefix Sum + Two PointersO(n)O(n)Useful when prefix arrays are already needed for multiple substring queries

Video Solution

2904. Shortest and Lexicographically Smallest Beautiful String 🔥 || Brute-Optimal (Sliding Window) 🔥 • Ayush Rao • 1,439 views views

Watch 8 more video solutions →

Frequently Asked Questions

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.
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.
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.
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.

Ready to solve this problem?

Practice Shortest and Lexicographically Smallest Beautiful String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring