Shortest and Lexicographically Smallest Beautiful String
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating every possible substring of the input string s, checking if it's "beautiful" (contains exactly k ones), and keeping track of the best one found so far based on the problem's criteria (shortest, then lexicographically smallest).
Algorithm
- Initialize
minLengthto a very large value andresultto an empty string. - Use two nested loops to generate all possible substrings. The outer loop
idetermines the start index, and the inner loopjdetermines the end index. - For each substring
s.substring(i, j + 1), create a third loop to count the number of '1's within it. - If the count of '1's equals
k, the substring is 'beautiful'. - Compare this beautiful substring with the current
result.- If its length is less than
minLength, updateminLengthand setresultto this new substring. - If its length is equal to
minLength, compare it lexicographically with the currentresultand updateresultif the new one is smaller.
- If its length is less than
- After checking all substrings, return the final
result.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. It systematically explores every single substring. The algorithm uses a pair of nested loops to define the start and end points of a substring. For each generated substring, it performs a check to see if it meets the 'beautiful' criteria by iterating through the substring and counting the '1's. If a substring is beautiful, it's compared against the best candidate found so far. A candidate is considered better if it's shorter, or if it's the same length but lexicographically smaller. This process continues until all O(N^2) substrings have been examined.
class Solution { public String shortestBeautifulSubstring(String s, int k) { String result = ""; int minLength = Integer.MAX_VALUE; for (int i = 0; i < s.length(); i++) { for (int j = i; j < s.length(); j++) { String sub = s.substring(i, j + 1); int onesCount = 0; for (char c : sub.toCharArray()) { if (c == '1') { onesCount++; } } if (onesCount == k) { if (sub.length() < minLength) { minLength = sub.length(); result = sub; } else if (sub.length() == minLength) { if (sub.compareTo(result) < 0) { result = sub; } } } } } return result; }}Complexity
Time
O(N^3), where N is the length of the string `s`. There are O(N^2) substrings, and for each substring, counting the '1's takes up to O(N) time.
Space
O(N), where N is the length of the string `s`. This space is used to store the candidate substrings.
Trade-offs
Pros
Simple to conceptualize and implement.
Cons
Highly inefficient due to three nested levels of iteration (or two loops with an O(N) operation inside).
Likely to result in a 'Time Limit Exceeded' (TLE) error for larger inputs.
A more optimized solution uses the sliding window technique. This approach maintains a "window" (a substring) and expands/shrinks it to efficiently find all beautiful substrings without the redundant calculations of the brute-force method.
Algorithm
- Initialize
leftandrightpointers to 0,onesCountto 0,minLengthto a large value, andresultto an empty string. - Iterate through the string with the
rightpointer from left to right to expand the window. - If
s.charAt(right)is a '1', incrementonesCount. - Use a
whileloop that runs as long asonesCountis equal tok. This condition indicates the current window[left, right]is a beautiful substring.- Inside the
whileloop, get the current substring and compare it with theresultto see if it's a better candidate (shorter or lexicographically smaller). - After checking, shrink the window from the left by incrementing the
leftpointer. If the character at the oldleftposition was a '1', decrementonesCount. - The
whileloop continues to shrink the window as long as it remains beautiful, finding all beautiful substrings ending at the currentright.
- Inside the
- After the main loop finishes, return the
result.
Walkthrough
The sliding window approach uses two pointers, left and right, to define the current substring under consideration. The right pointer always moves forward, expanding the window. We maintain a count of '1's within this window. When the count of '1's reaches k, we have found a beautiful substring. At this point, we can potentially shrink the window from the left. We check if the current window is the best solution so far. Then, we advance the left pointer. If the character leaving the window is a '1', we decrement our count. This allows us to efficiently transition from one beautiful substring to another.
class Solution { public String shortestBeautifulSubstring(String s, int k) { String result = ""; int minLength = Integer.MAX_VALUE; int left = 0; int onesCount = 0; for (int right = 0; right < s.length(); right++) { if (s.charAt(right) == '1') { onesCount++; } while (onesCount == k) { String candidate = s.substring(left, right + 1); if (candidate.length() < minLength) { minLength = candidate.length(); result = candidate; } else if (candidate.length() == minLength) { if (candidate.compareTo(result) < 0) { result = candidate; } } if (s.charAt(left) == '1') { onesCount--; } left++; } } return result; }}Complexity
Time
O(N^2) in the worst case. Although each pointer moves at most N times, the substring creation and comparison inside the loop can take O(N) time, leading to a quadratic complexity.
Space
O(N) to store the result and candidate strings.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Avoids redundant counting of '1's for overlapping substrings.
Cons
The time complexity is still quadratic in the worst case due to repeated substring creation and comparison inside the loop.
This is the most efficient approach, which builds upon a key insight: any shortest beautiful substring must necessarily start and end with a '1'. By pre-calculating the indices of all '1's, we can drastically reduce the number of substrings we need to check.
Algorithm
- First, iterate through the string
sto find and store the indices of all '1's in a list, let's call itoneIndices. - If the size of
oneIndicesis less thank, it's impossible to form a beautiful substring, so return an empty string. - Initialize
minLengthto a large value andresultto an empty string. - Iterate through the
oneIndiceslist fromi = 0tooneIndices.size() - k. - For each
i, thei-th '1' and the(i + k - 1)-th '1' form the boundaries of a minimal beautiful substring. The start index insisoneIndices.get(i)and the end index isoneIndices.get(i + k - 1). - Calculate the length of this candidate substring.
- Compare its length and lexicographical order with the current
resultand update if it's a better candidate. - After checking all
m-k+1such minimal substrings, return the finalresult.
Walkthrough
This optimized method focuses only on the substrings that are viable candidates for being the shortest. A simple observation reveals that if a beautiful substring starts or ends with '0', we can always trim that '0' to get a shorter beautiful substring. Therefore, the shortest beautiful substring must start and end with '1'.
Based on this, the algorithm first scans the string to collect the indices of all '1's. Then, it slides a window of size k over this list of indices. Each window of k indices defines a minimal beautiful substring—one that starts with the first '1' in the window and ends with the last '1'. We compare all such minimal substrings to find the one that is shortest and lexicographically smallest.
import java.util.ArrayList;import java.util.List; class Solution { public String shortestBeautifulSubstring(String s, int k) { List<Integer> oneIndices = new ArrayList<>(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '1') { oneIndices.add(i); } } if (oneIndices.size() < k) { return ""; } String result = ""; int minLength = Integer.MAX_VALUE; for (int i = 0; i <= oneIndices.size() - k; i++) { int start = oneIndices.get(i); int end = oneIndices.get(i + k - 1); int len = end - start + 1; if (len < minLength) { minLength = len; result = s.substring(start, end + 1); } else if (len == minLength) { String candidate = s.substring(start, end + 1); if (candidate.compareTo(result) < 0) { result = candidate; } } } return result; }}Complexity
Time
O(N + M*N), where N is the string length and M is the number of '1's. O(N) for finding indices, and the loop runs M-k+1 times with O(N) work inside. In the worst case (M ≈ N), this is O(N^2), but it's practically much faster than the general sliding window if M is small.
Space
O(M), where M is the number of '1's in the string, to store the indices. In the worst case, this is O(N).
Trade-offs
Pros
The most efficient approach by significantly pruning the search space.
Conceptually clean, as it directly targets the properties of the optimal solution.
Cons
Requires extra space to store the indices of all '1's.
Solutions
Solution
class Solution {public String shortestBeautifulSubstring(String s, int k) { int n = s.length(); String ans = ""; for (int i = 0; i < n; ++i) { for (int j = i + k; j <= n; ++j) { String t = s.substring(i, j); int cnt = 0; for (char c : t.toCharArray()) { cnt += c - '0'; } if (cnt == k && ("".equals(ans) || j - i < ans.length() || (j - i == ans.length() && t.compareTo(ans) < 0))) { ans = t; } } } return ans; }}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 ansclass Solution {public: string shortestBeautifulSubstring(string s, int k) { int n = s.size(); string ans = ""; for (int i = 0; i < n; ++i) { for (int j = i + k; j <= n; ++j) { string t = s.substr(i, j - i); int cnt = count(t.begin(), t.end(), '1'); if (cnt == k && (ans == "" || j - i < ans.size() || (j - i == ans.size() && t < ans))) { ans = t; } } } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.