2904. Shortest and Lexicographically Smallest Beautiful String
Problem Description
You're tasked to find the lexicographically smallest "beautiful" substring within a binary string s
which contains exactly k
occurrences of the character '1'. A "beautiful" substring is defined as having exactly k
number of '1's within it. If no substring matches this criterion, you need to return an empty string.
The lexicographical order here refers to the natural dictionary order where a string is compared character by character from the left and as soon as a difference is found, the comparison is decided by the difference in those characters like following "abcd" and "abcc", 'd' is greater than 'c'.
For example, consider the binary string s = "001101"
and k = 2
. The "beautiful" substrings that contain exactly two '1's are "0110", "1101", and "101". The shortest of these is "101", which is also the lexicographically smallest one. Therefore, "101" is the answer.
Intuition
To solve the problem, we have to efficiently find the shortest "beautiful" substrings and among them determine the one that is smallest lexicographically. The brute-force or enumeration method would be to check all possible substrings which would be very slow for longer strings because we'd need to compare a vast number of substrings. To optimize, we can use a sliding-window approach, accomplished using two pointers, to identify "beautiful" substrings.
Here's how the two-pointer approach helps in finding the solution:
- Use the
i
pointer to mark the beginning of your current window (initially at the start of the string) andj
to mark the end (also initially at the start). - The
cnt
variable tracks the count of '1's in the current window. The window extends (by increasingj
) until thecnt
of '1's is equal tok
. - During this extension, if
cnt
exceedsk
, or if the current window starts with '0', we movei
ahead to try and find a smaller window withk
number of '1's. - Once we find a window with exactly
k
'1's, we compare it to the current answer. For this, we have three conditions:- If there's no answer yet, the current window is our new answer.
- If the length of the current window is less than the length of the current answer, then the current window becomes our new answer (since shorter is better).
- If the current window is the same length as the answer but lexicographically smaller, then the current window becomes the new answer.
By the end, our sliding window will have given us the lexicographically smallest "beautiful" substring that is of the shortest length.
Learn more about Sliding Window patterns.
Solution Approach
The provided solution uses a two-pointer approach, which is a pattern commonly used to efficiently process subarrays or substrings of a given array or string. Here's a detailed step-by-step explanation of the algorithm based on the reference solution approach:
- Initialize two pointers,
i
andj
, which represent the start and end of a sliding window, to0
. Also, initialize a countercnt
to0
to count the number of '1's within the window, and an empty stringans
to keep track of the current answer. - Slide the right boundary of the window (represented by
j
) to the right by incrementingj
in a loop until the end of the string. Updatecnt
by checking if the current characters[j]
is '1'. - If
cnt
exceedsk
, or if the current window starts with '0' (not a valid start for the beautiful substring), slide the left boundary of the window (represented byi
) to the right until the window is beautiful again. This step ensures we always have a valid beautiful substring within the window or an empty window ready to grow. - Whenever
cnt
equalsk
, check if we found a smaller or lexicographically smaller beautiful substring than the current answer. If so, update theans
.not ans
: No answer has been found yet, so any found substring becomes the new answer.j - i < len(ans)
: Found a shorter beautiful substring.(j - i == len(ans) and s[i:j] < ans)
: Found an equally short but lexicographically smaller beautiful substring.
- Continue the above process until
j
reaches the end of the string. At this point, the smallest lexicographically beautiful substring is stored inans
.
The main data structure used here is a string to keep the current answer for comparison. No extra space is required apart from the input, making the space complexity O(1)
, not considering the input and output strings.
The time complexity is O(n)
, where n
is the length of the string s
. This is because each character in s
is visited at most twice: once when expanding the right boundary (j
), and once when contracting the left boundary (i
).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach described.
Suppose we are given the binary string s = "0101101"
and k = 3
. We need to find the smallest lexicographically "beautiful" substring that contains exactly three '1's.
- Initialize
i
andj
to0
,cnt
to0
(count of '1's in the current window), andans
as an empty string. - We advance
j
from0
to6
(end of the string) in a loop:- At
j=0
:s[j]='0'
, socnt
remains0
. - At
j=1
:s[j]='1'
, so incrementcnt
to1
. - At
j=2
:s[j]='0'
, socnt
remains1
. - At
j=3
:s[j]='1'
, incrementcnt
to2
. - At
j=4
:s[j]='1'
, incrementcnt
to3
. Now we have a "beautiful" substring "0101" from indexi=0
toj=4
.
- At
- We update
ans
to "0101" because theans
is currently empty. - We continue to increment
j
:- At
j=5
:s[j]='0'
, socnt
remains3
. The substring "01010" is longer than "0101", we don't updateans
. - At
j=6
:s[j]='1'
and nowcnt
exceedsk
(it's4
now). We need to adjust the window.
- At
- To adjust the window, we slide
i
to the right to decreasecnt
back tok
:- Increment
i
to1
:s[i-1]='0'
, socnt
remains4
. - Increment
i
to2
:s[i-1]='1'
, decrementcnt
to3
. Now, the substring is "10101" from indexi=2
toj=6
.
- Increment
- Check if the new window is smaller or lexicographically smaller than
ans
but since it's not, we do not updateans
. - As
j
has reached the end ofs
, the loop ends, and the smallest lexicographically "beautiful" substring found is "0101" which is stored inans
.
Therefore, for the string s = "0101101"
with k = 3
, the output will be "0101". This approach ensures we scan the string only once, and efficiently find the substring we're looking for.
Solution Implementation
1class Solution:
2 def shortestBeautifulSubstring(self, s: str, k: int) -> str:
3 # Initialize pointers and counter
4 left_pointer = right_pointer = count_ones = 0
5 length_of_s = len(s)
6 shortest_substring = ""
7
8 # Iterate over the string while maintaing a sliding window
9 while right_pointer < length_of_s:
10 # Count occurrences of '1'
11 count_ones += s[right_pointer] == "1"
12
13 # If we have more than k '1's or the current character is '0',
14 # shrink the window from the left
15 while count_ones > k or (left_pointer < right_pointer and s[left_pointer] == "0"):
16 count_ones -= s[left_pointer] == "1"
17 left_pointer += 1
18
19 # Move the right end of the window forward
20 right_pointer += 1
21
22 # Check if we have found a valid beautiful substring
23 # with exactly k '1's and update answer if it's the shortest seen so far,
24 # or if it's lexicographically smaller than the current best with equal length.
25 if count_ones == k and (
26 not shortest_substring or
27 right_pointer - left_pointer < len(shortest_substring) or
28 (right_pointer - left_pointer == len(shortest_substring) and s[left_pointer:right_pointer] < shortest_substring)
29 ):
30 shortest_substring = s[left_pointer:right_pointer]
31
32 # Return the shortest beautiful substring found
33 return shortest_substring
34
1class Solution {
2 public String shortestBeautifulSubstring(String s, int k) {
3 int start = 0; // 'start' is the beginning index of the current substring
4 int end = 0; // 'end' is the ending index of the current substring (exclusive)
5 int count = 0; // Count of current number of '1's
6 int n = s.length(); // Length of the string 's'
7 String answer = ""; // Initialize the answer as an empty string
8
9 // Iterate through the string 's' with 'end' as the right boundary
10 while (end < n) {
11 // Increase count if the current character is '1'
12 count += s.charAt(end) - '0';
13
14 // Shrink the window from the left if the count is greater than 'k'
15 // or if the leading character is '0' and the window size is greater than 1.
16 while (count > k || (start < end && s.charAt(start) == '0')) {
17 count -= s.charAt(start) - '0'; // Decrease the count while moving 'start' to the right
18 ++start; // Move the start index to the right
19 }
20
21 ++end; // Move the end index to the right
22
23 // Get the current substring from start to end
24 String currentSubstring = s.substring(start, end);
25
26 // Check if the current substring is beautiful,
27 // and if it's the shortest one seen so far or lexicographically smaller.
28 if (count == k && (answer.isEmpty() || end - start < answer.length() ||
29 (end - start == answer.length() && currentSubstring.compareTo(answer) < 0))) {
30 answer = currentSubstring; // Update the answer with the current substring
31 }
32 }
33 // Return the shortest lexicographically smallest beautiful substring found
34 return answer;
35 }
36}
37
1class Solution {
2public:
3 // Function that returns the shortest substring which contains 'k' number of '1's
4 string shortestBeautifulSubstring(string str, int k) {
5 int startIndex = 0, endIndex = 0, oneCount = 0;
6 int strSize = str.size();
7 string shortestSubstring = "";
8
9 // Iterate over the string to find the valid substrings
10 while (endIndex < strSize) {
11 // Increment oneCount if current character is '1'
12 oneCount += (str[endIndex] == '1');
13
14 // Shrink the window from the left if
15 // we have more than k '1's or the current
16 // window starts with a '0'
17 while (oneCount > k || (startIndex < endIndex && str[startIndex] == '0')) {
18 oneCount -= (str[startIndex++] == '1');
19 }
20
21 // Move to the next character in the string
22 ++endIndex;
23
24 // Extract the current valid substring
25 string currentSubstring = str.substr(startIndex, endIndex - startIndex);
26
27 // Check if the current substring satisfies the conditions:
28 // 1) It contains exactly k '1's
29 // 2) It is shorter than the previously recorded shortest substring
30 // 3) Or, it is the same length as the previously recorded shortest
31 // substring but lexicographically smaller
32 if (oneCount == k &&
33 (shortestSubstring.empty() || endIndex - startIndex < shortestSubstring.size() ||
34 (endIndex - startIndex == shortestSubstring.size() && currentSubstring < shortestSubstring))) {
35 shortestSubstring = currentSubstring;
36 }
37 }
38
39 // Return the shortest substring that meets the conditions
40 return shortestSubstring;
41 }
42};
43
1function shortestBeautifulSubstring(word: string, threshold: number): string {
2 let startIndex = 0; // Start index of the current substring
3 let endIndex = 0; // End index of the current substring
4 let oneCount = 0; // Count of '1's in the current substring
5 const length = word.length; // Length of the input string
6 let answer: string = ''; // The shortest beautiful substring found
7
8 // Traverse the string
9 while (endIndex < length) {
10 // Increase count if '1' is found
11 oneCount += word[endIndex] === '1' ? 1 : 0;
12
13 // Shrink the window from the left if the count of '1's is more than the threshold
14 // or if the current character is '0' and the window size is more than 1
15 while (oneCount > threshold || (startIndex < endIndex && word[startIndex] === '0')) {
16 oneCount -= word[startIndex] === '1' ? 1 : 0;
17 startIndex++;
18 }
19
20 // Move to next character in the string
21 endIndex++;
22
23 // Get the current substring from startIndex to endIndex (non-inclusive)
24 const currentSubstring = word.slice(startIndex, endIndex);
25
26 // If count of '1's equals threshold, and there is no answer yet or current substring is
27 // shorter or lexicographically smaller than the previous answer, update the answer
28 if (oneCount === threshold && (answer === '' || endIndex - startIndex < answer.length || (endIndex - startIndex === answer.length && currentSubstring < answer))) {
29 answer = currentSubstring;
30 }
31 }
32
33 // Return the shortest beautiful substring
34 return answer;
35}
36
Time and Space Complexity
The time complexity of the given code is O(n)
where n
is the length of the string s
. This is because there are two pointers i
and j
, and each pointer only moves from the beginning to the end of the string in a linear fashion. There are no nested loops, and each character of the string is processed at most twice (once when j
increments and potentially once when i
increments).
The space complexity of the code is O(1)
if we only take into account the space used for variables and pointers, which is constant and does not depend on the input size. If we consider the space required for the output string ans
, in the worst case it could be as large as the input string, leading to a space complexity of O(n)
where n
is the length of the string s
.
Learn more about how to find time and space complexity quickly using problem constraints.
How many ways can you arrange the three letters A, B and C?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!