Shortest and Lexicographically Smallest Beautiful String solution and explanation
8 more videos on this problem
2904. Shortest and Lexicographically Smallest Beautiful String 🔥 || Brute-Optimal (Sliding Window) 🔥Ayush Rao · 6:46 · 1K views
100084. Shortest and Lexicographically Smallest Beautiful String | Leetcode | Weekly Contest 367.Optimization · 0:30 · 848 views
Leetcode Weekly Contest 367 | Shortest and Lexicographically Smallest Beautiful String | PythonBayu Aji · 1:59 · 616 views
2904. Shortest and Lexicographically Smallest Beautiful String (Leetcode Medium)Programming Live with Larry · 8:20 · 466 views
2904. Shortest and Lexicographically Smallest Beautiful String | LEETCODE WEEKLY CONTEST 367code Explainer · 12:16 · 443 views
2904. Shortest and Lexicographically Smallest Beautiful string | Leetcode weekly contestRuntime Error · 16:20 · 359 views
Shortest and Lexicographically Smallest Beautiful String | Leetcode Contest 367 | JavacodeSolution · 6:22 · 121 views
LEETCODE weekly-contest-367 | 2904 Shortest & Lexicographically Smallest Beautiful String | 15.10.23CodingVerse · 11:51 · 40 views
100084 Shortest & Lexicographically Smallest Beautiful String leetcode contest365 contest solutionSsquare · 1:12 · 335 views
The 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, anddis greater thanc.
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 <= 1001 <= 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.
def find_beautiful_substring(s, k):
n = len(s)
l, r = 0, 0
count_ones = 0
min_substring = ""
while r < n:
if s[r] == '1':
count_ones += 1
while count_ones > k:
if s[l] == '1':
count_ones -= 1
l += 1
if count_ones == k:
current = s[l:r+1]
if not min_substring or len(current) < len(min_substring) or (len(current) == len(min_substring) and current < min_substring):
min_substring = current
r += 1
return min_substring
s = "100011001"
k = 3
print(find_beautiful_substring(s, k))public class BeautifulSubstring {
public static String findBeautifulSubstring(String s, int k) {
int n = s.length(), l = 0, r = 0, countOnes = 0;
String minSubstring = "";
while (r < n) {
if (s.charAt(r) == '1') countOnes++;
while (countOnes > k) {
if (s.charAt(l) == '1') countOnes--;
l++;
}
if (countOnes == k) {
String current = s.substring(l, r + 1);
if (minSubstring.isEmpty() || current.length() < minSubstring.length() ||
(current.length() == minSubstring.length() && current.compareTo(minSubstring) < 0)) {
minSubstring = current;
}
}
r++;
}
return minSubstring;
}
public static void main(String[] args) {
String s = "100011001";
int k = 3;
System.out.println(findBeautifulSubstring(s, k));
}
}#include <iostream>
#include <string>
#include <limits>
using namespace std;
string findBeautifulSubstring(const string &s, int k) {
int n = s.size(), l = 0, r = 0, count_ones = 0;
string min_substring = "";
while (r < n) {
if (s[r] == '1') count_ones++;
while (count_ones > k) {
if (s[l] == '1') count_ones--;
l++;
}
if (count_ones == k) {
string current = s.substr(l, r - l + 1);
if (min_substring.empty() || current.size() < min_substring.size() || (current.size() == min_substring.size() && current < min_substring)) {
min_substring = current;
}
}
++r;
}
return min_substring;
}
int main() {
string s = "100011001";
int k = 3;
cout << findBeautifulSubstring(s, k) << endl;
return 0;
}function findBeautifulSubstring(s, k) {
let n = s.length, l = 0, r = 0, countOnes = 0;
let minSubstring = "";
while (r < n) {
if (s[r] === '1') countOnes++;
while (countOnes > k) {
if (s[l] === '1') countOnes--;
l++;
}
if (countOnes === k) {
let current = s.slice(l, r + 1);
if (!minSubstring || current.length < minSubstring.length || (current.length === minSubstring.length && current < minSubstring)) {
minSubstring = current;
}
}
r++;
}
return minSubstring;
}
let s = "100011001";
let k = 3;
console.log(findBeautifulSubstring(s, k));#include <stdio.h>
#include <string.h>
char* findBeautifulSubstring(char* s, int k) {
int n = strlen(s);
int l = 0, r = 0;
int count_ones = 0;
int min_len = n + 1;
char *result = "";
char buffer[101] = {0};
while (r < n) {
if (s[r] == '1') count_ones++;
while (count_ones > k) {
if (s[l] == '1') count_ones--;
l++;
}
if (count_ones == k) {
int curr_len = r - l + 1;
if (curr_len < min_len || (curr_len == min_len && strncmp(s + l, buffer, curr_len) < 0)) {
min_len = curr_len;
strncpy(buffer, s + l, curr_len);
buffer[curr_len] = '\0';
result = buffer;
}
}
r++;
}
return result;
}
int main() {
char s[] = "100011001";
int k = 3;
printf("%s\n", findBeautifulSubstring(s, k));
return 0;
}using System;
public class BeautifulSubstring {
public static string FindBeautifulSubstring(string s, int k) {
int n = s.Length, l = 0, r = 0, countOnes = 0;
string minSubstring = "";
while (r < n) {
if (s[r] == '1') countOnes++;
while (countOnes > k) {
if (s[l] == '1') countOnes--;
l++;
}
if (countOnes == k) {
string current = s.Substring(l, r - l + 1);
if (minSubstring == "" || current.Length < minSubstring.Length ||
(current.Length == minSubstring.Length && string.Compare(current, minSubstring) < 0)) {
minSubstring = current;
}
}
r++;
}
return minSubstring;
}
public static void Main() {
string s = "100011001";
int k = 3;
Console.WriteLine(FindBeautifulSubstring(s, k));
}
}This Python solution employs the sliding window technique to efficiently search for and update the shortest beautiful substring with exactly k '1's. It relies on slicing the string with Python's array slicing capabilities.
Time Complexity: O(n). We iterate over the string with two pointers.
Space Complexity: O(k) for the resulting substring that meets the condition.
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.
def find_beautiful_substring(s, k):
n = len(s)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + (1 if s[i] == '1' else 0)
l, r = 0, 0
min_substring = ""
while r <= n:
if prefix[r] - prefix[l] == k:
current = s[l:r]
if not min_substring or len(current) < len(min_substring) or (len(current) == len(min_substring) and current < min_substring):
min_substring = current
l += 1
elif prefix[r] - prefix[l] < k:
r += 1
else:
l += 1
return min_substring
s = "100011001"
k = 3
print(find_beautiful_substring(s, k))public class BeautifulSubstring {
public static String findBeautifulSubstring(String s, int k) {
int n = s.length();
int[] prefix = new int[n+1];
for (int i = 0; i < n; i++) {
prefix[i+1] = prefix[i] + (s.charAt(i) == '1' ? 1 : 0);
}
int l = 0, r = 0;
String minSubstring = "";
while (r <= n) {
if (prefix[r] - prefix[l] == k) {
String current = s.substring(l, r);
if (minSubstring.isEmpty() || current.length() < minSubstring.length() ||
(current.length() == minSubstring.length() && current.compareTo(minSubstring) < 0)) {
minSubstring = current;
}
l++;
} else if (prefix[r] - prefix[l] < k) {
r++;
} else {
l++;
}
}
return minSubstring;
}
public static void main(String[] args) {
String s = "100011001";
int k = 3;
System.out.println(findBeautifulSubstring(s, k));
}
}#include <iostream>
#include <vector>
using namespace std;
string findBeautifulSubstring(const string &s, int k) {
int n = s.size();
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + (s[i] == '1');
}
int l = 0, r = 0;
string minSubstring = "";
while (r <= n) {
if (prefix[r] - prefix[l] == k) {
string current = s.substr(l, r - l);
if (minSubstring.empty() || current.size() < minSubstring.size() || (current.size() == minSubstring.size() && current < minSubstring)) {
minSubstring = current;
}
l++;
} else if (prefix[r] - prefix[l] < k) {
r++;
} else {
l++;
}
}
return minSubstring;
}
int main() {
string s = "100011001";
int k = 3;
cout << findBeautifulSubstring(s, k) << endl;
return 0;
}function findBeautifulSubstring(s, k) {
let n = s.length;
let prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + (s[i] === '1' ? 1 : 0);
}
let l = 0, r = 0;
let minSubstring = "";
while (r <= n) {
if (prefix[r] - prefix[l] === k) {
let current = s.slice(l, r);
if (!minSubstring || current.length < minSubstring.length || (current.length === minSubstring.length && current < minSubstring)) {
minSubstring = current;
}
l++;
} else if (prefix[r] - prefix[l] < k) {
r++;
} else {
l++;
}
}
return minSubstring;
}
let s = "100011001";
let k = 3;
console.log(findBeautifulSubstring(s, k));#include <stdio.h>
#include <string.h>
char* findBeautifulSubstring(char* s, int k) {
int n = strlen(s);
int prefix[n+1];
prefix[0] = 0;
for (int i = 0; i < n; i++) {
prefix[i+1] = prefix[i] + (s[i] == '1');
}
int l = 0, r = 0;
char *result = "";
char buffer[101] = {0};
int min_len = n + 1;
while (r <= n) {
if (prefix[r] - prefix[l] == k) {
int current_len = r - l;
if (current_len < min_len || (current_len == min_len && strncmp(s + l, buffer, current_len) < 0)) {
min_len = current_len;
strncpy(buffer, s + l, current_len);
buffer[current_len] = '\0';
result = buffer;
}
l++;
} else if (prefix[r] - prefix[l] < k) {
r++;
} else {
l++;
}
}
return result;
}
int main() {
char s[] = "100011001";
int k = 3;
printf("%s\n", findBeautifulSubstring(s, k));
return 0;
}using System;
public class BeautifulSubstring {
public static string FindBeautifulSubstring(string s, int k) {
int n = s.Length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + (s[i] == '1' ? 1 : 0);
}
int l = 0, r = 0;
string minSubstring = "";
while (r <= n) {
if (prefix[r] - prefix[l] == k) {
string current = s.Substring(l, r - l);
if (string.IsNullOrEmpty(minSubstring) || current.Length < minSubstring.Length ||
(current.Length == minSubstring.Length && string.Compare(current, minSubstring) < 0)) {
minSubstring = current;
}
l++;
} else if (prefix[r] - prefix[l] < k) {
r++;
} else {
l++;
}
}
return minSubstring;
}
public static void Main() {
string s = "100011001";
int k = 3;
Console.WriteLine(FindBeautifulSubstring(s, k));
}
}By implementing prefix sums, the Python solution can pinpoint sections of s that contain exactly k '1's and optimize the search for the desired substring.
Time Complexity: O(n), where n stands for the string length, handling both prefix sums and pointer processing. Space Complexity: O(n) for the prefix sum storage.
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.
function shortestBeautifulSubstring(s: string, k: number): string {
const n = s.length;
let ans: string = '';
for (let i = 0; i < n; ++i) {
for (let j = i + k; j <= n; ++j) {
const t = s.slice(i, j);
const cnt = t.split('').filter(c => c === '1').length;
if (
cnt === k &&
(ans === '' || j - i < ans.length || (j - i === ans.length && t < ans))
) {
ans = t;
}
}
}
return ans;
}func shortestBeautifulSubstring(s string, k int) (ans string) {
n := len(s)
for i := 0; i < n; i++ {
for j := i + k; j <= n; j++ {
t := s[i:j]
cnt := 0
for _, c := range t {
if c == '1' {
cnt++
}
}
if cnt == k && (ans == "" || j-i < len(ans) || (j-i == len(ans) && t < ans)) {
ans = t
}
}
}
return
}impl Solution {
pub fn shortest_beautiful_substring(s: String, k: i32) -> String {
let n = s.len();
let mut ans = String::new();
for i in 0..n {
for j in i + (k as usize)..=n {
let t = &s[i..j];
if (t.matches('1').count() as i32) == k
&& (ans.is_empty() || j - i < ans.len() || (j - i == ans.len() && t < &ans))
{
ans = t.to_string();
}
}
}
ans
}
}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.
function shortestBeautifulSubstring(s: string, k: number): string {
let [i, j, cnt] = [0, 0, 0];
const n = s.length;
let ans: string = '';
while (j < n) {
cnt += s[j] === '1' ? 1 : 0;
while (cnt > k || (i < j && s[i] === '0')) {
cnt -= s[i++] === '1' ? 1 : 0;
}
++j;
const t = s.slice(i, j);
if (cnt === k && (ans === '' || j - i < ans.length || (j - i === ans.length && t < ans))) {
ans = t;
}
}
return ans;
}func shortestBeautifulSubstring(s string, k int) (ans string) {
i, j, cnt := 0, 0, 0
n := len(s)
for j < n {
cnt += int(s[j] - '0')
for cnt > k || (i < j && s[i] == '0') {
cnt -= int(s[i] - '0')
i++
}
j++
t := s[i:j]
if cnt == k && (ans == "" || j-i < len(ans) || (j-i == len(ans) && t < ans)) {
ans = t
}
}
return
}impl Solution {
pub fn shortest_beautiful_substring(s: String, k: i32) -> String {
let s_chars: Vec<char> = s.chars().collect();
let mut i = 0;
let mut j = 0;
let mut cnt = 0;
let mut ans = String::new();
let n = s.len();
while j < n {
if s_chars[j] == '1' {
cnt += 1;
}
while cnt > k || (i < j && s_chars[i] == '0') {
if s_chars[i] == '1' {
cnt -= 1;
}
i += 1;
}
j += 1;
if cnt == k
&& (ans.is_empty() || j - i < ans.len() || (j - i == ans.len() && &s[i..j] < &ans))
{
ans = s_chars[i..j].iter().collect();
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Technique | Time Complexity: O(n). We iterate over the string with two pointers. |
| Prefix Sum and Two Pointers | Time Complexity: O(n), where |
| Enumeration | – |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Technique | O(n) | O(1) | Best general solution for scanning substrings with constraints like exactly k ones |
| Prefix Sum + Two Pointers | O(n) | O(n) | Useful when prefix arrays are already needed for multiple substring queries |
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.