Shortest and Lexicographically Smallest Beautiful String
MediumUpdated: Aug 2, 2025
Practice on:
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 lexicographicallysmallest beautiful substring of string _s
with length equal tolen. If s doesn't contain a beautiful substring, return anempty 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.
Examples
Example 1
Input: s = "100011001", k = 3
Output: "11001"
Explanation: There are 7 beautiful substrings in this example:
1. The substring "_100011_ 001".
2. The substring "_1000110_ 01".
3. The substring "_10001100_ 1".
4. The substring "1 _00011001_ ".
5. The substring "10 _0011001_ ".
6. The substring "100 _011001_ ".
7. The substring "1000 _11001_ ".
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 "_101_ 1".
2. The substring "1 _011_ ".
3. The substring "10 _11_ ".
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
Solution
Method 1 – Sliding Window
Intuition
We want the shortest substring with exactly k '1's, and among those, the lexicographically smallest. We can use a sliding window to find all substrings with exactly k '1's, track the minimum length, and then among those, pick the smallest lexicographically.
Approach
- Use two pointers (left, right) to maintain a window and a counter for '1's.
- Expand right, incrementing the count of '1's.
- When the count reaches k, try to shrink the window from the left as much as possible while keeping exactly k '1's.
- For each valid window, if its length is less than the current minimum, update the answer. If equal, update if lexicographically smaller.
- Return the answer after checking all windows.
Code
C++
class Solution {
public:
string shortestBeautifulSubstring(string s, int k) {
int n = s.size(), cnt = 0, l = 0, minLen = n + 1;
string ans = "";
for (int r = 0; r < n; ++r) {
if (s[r] == '1') ++cnt;
while (cnt > k) {
if (s[l++] == '1') --cnt;
}
if (cnt == k) {
while (s[l] != '1') ++l;
int len = r - l + 1;
string sub = s.substr(l, len);
if (len < minLen || (len == minLen && sub < ans)) {
minLen = len;
ans = sub;
}
}
}
return ans;
}
};
Go
func shortestBeautifulSubstring(s string, k int) string {
n := len(s)
cnt, l, minLen := 0, 0, n+1
ans := ""
for r := 0; r < n; r++ {
if s[r] == '1' {
cnt++
}
for cnt > k {
if s[l] == '1' {
cnt--
}
l++
}
if cnt == k {
for s[l] != '1' {
l++
}
if r-l+1 < minLen || (r-l+1 == minLen && s[l:r+1] < ans) {
minLen = r - l + 1
ans = s[l : r+1]
}
}
}
return ans
}
Java
class Solution {
public String shortestBeautifulSubstring(String s, int k) {
int n = s.length(), cnt = 0, l = 0, minLen = n + 1;
String ans = "";
for (int r = 0; r < n; ++r) {
if (s.charAt(r) == '1') ++cnt;
while (cnt > k) {
if (s.charAt(l++) == '1') --cnt;
}
if (cnt == k) {
while (s.charAt(l) != '1') ++l;
int len = r - l + 1;
String sub = s.substring(l, r + 1);
if (len < minLen || (len == minLen && sub.compareTo(ans) < 0)) {
minLen = len;
ans = sub;
}
}
}
return ans;
}
}
Kotlin
class Solution {
fun shortestBeautifulSubstring(s: String, k: Int): String {
val n = s.length
var cnt = 0
var l = 0
var minLen = n + 1
var ans = ""
for (r in 0 until n) {
if (s[r] == '1') cnt++
while (cnt > k) {
if (s[l++] == '1') cnt--
}
if (cnt == k) {
while (s[l] != '1') l++
val len = r - l + 1
val sub = s.substring(l, r + 1)
if (len < minLen || (len == minLen && sub < ans)) {
minLen = len
ans = sub
}
}
}
return ans
}
}
Python
class Solution:
def shortestBeautifulSubstring(self, s: str, k: int) -> str:
n = len(s)
cnt = l = 0
min_len = n + 1
ans = ''
for r in range(n):
if s[r] == '1':
cnt += 1
while cnt > k:
if s[l] == '1':
cnt -= 1
l += 1
if cnt == k:
while s[l] != '1':
l += 1
length = r - l + 1
sub = s[l:r+1]
if length < min_len or (length == min_len and (ans == '' or sub < ans)):
min_len = length
ans = sub
return ans
Rust
impl Solution {
pub fn shortest_beautiful_substring(s: String, k: i32) -> String {
let s = s.as_bytes();
let n = s.len();
let mut cnt = 0;
let mut l = 0;
let mut min_len = n + 1;
let mut ans = String::new();
for r in 0..n {
if s[r] == b'1' { cnt += 1; }
while cnt > k {
if s[l] == b'1' { cnt -= 1; }
l += 1;
}
if cnt == k {
while s[l] != b'1' { l += 1; }
let len = r - l + 1;
let sub = &s[l..=r];
let sub_str = String::from_utf8(sub.to_vec()).unwrap();
if len < min_len || (len == min_len && (ans.is_empty() || sub_str < ans)) {
min_len = len;
ans = sub_str;
}
}
}
ans
}
}
TypeScript
class Solution {
shortestBeautifulSubstring(s: string, k: number): string {
const n = s.length;
let cnt = 0, l = 0, minLen = n + 1;
let ans = '';
for (let r = 0; r < n; ++r) {
if (s[r] === '1') ++cnt;
while (cnt > k) {
if (s[l++] === '1') --cnt;
}
if (cnt === k) {
while (s[l] !== '1') ++l;
const len = r - l + 1;
const sub = s.slice(l, r + 1);
if (len < minLen || (len === minLen && (ans === '' || sub < ans))) {
minLen = len;
ans = sub;
}
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n^2), where n = length of s. In the worst case, the window can move O(n) times for each right pointer. - 🧺 Space complexity:
O(n), for storing the answer substring.