LeetCode 2904: Shortest and Lexicographically Smallest Beautiful String
LeetCode 2904 Solution Explanation
Explanation:
To solve this problem, we can use a sliding window approach. We iterate through the input string s and maintain a window of size k to count the number of ones in each substring. If the count of ones in the window is equal to k, we update the result string to be the lexicographically smallest substring of length k encountered so far. We keep track of the start index of the window and move the window one step at a time. If the count of ones in the window is less than k, we expand the window. If the count exceeds k, we contract the window.
At the end of the iteration, we return the lexicographically smallest substring found or an empty string if no beautiful substring is present in the input string s.
- Time complexity: O(n), where n is the length of the input string
s. - Space complexity: O(1)
:
LeetCode 2904 Solutions in Java, C++, Python
class Solution {
public String shortestBeautifulString(String s, int k) {
String res = "";
int count = 0, start = 0, minLen = Integer.MAX_VALUE;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '1') {
count++;
}
while (count == k) {
if (i - start + 1 < minLen) {
minLen = i - start + 1;
res = s.substring(start, i + 1);
}
if (s.charAt(start) == '1') {
count--;
}
start++;
}
}
return res;
}
}Interactive Code Editor for LeetCode 2904
Improve Your LeetCode 2904 Solution
Use the editor below to refine the provided solution for LeetCode 2904. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...