MediumNo. 2904
Shortest and Lexicographically Smallest Beautiful String — LeetCode 2904 Python Solution
- Pattern
- Sliding Window
- Topics
- String, Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
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.
Example
- Input
- s = "100011001", k = 3
- Output
- "11001"
- Explanation
- There are 7 beautiful substrings in this example:
Python solution
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 ansComplexity
- Time
- O(n3)
- Space · auxiliary
- O(n)
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2904. Shortest and Lexicographically Smallest Beautiful String is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1044 | Longest Duplicate Substring | Hard |
| 1208 | Get Equal Substrings Within Budget | Medium |
| 1234 | Replace the Substring for Balanced String | Medium |
| 1456 | Maximum Number of Vowels in a Substring of Given Length | Medium |
| 1839 | Longest Substring Of All Vowels in Order | Medium |
| 1871 | Jump Game VII | Medium |
Frequently asked questions
- How hard is LeetCode 2904. Shortest and Lexicographically Smallest Beautiful String?
LeetCode 2904. Shortest and Lexicographically Smallest Beautiful String is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2904. Shortest and Lexicographically Smallest Beautiful String?
The Python solution on this page runs in O(n3).
- What is the space complexity of LeetCode 2904. Shortest and Lexicographically Smallest Beautiful String?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2904. Shortest and Lexicographically Smallest Beautiful String cover?
LeetCode 2904. Shortest and Lexicographically Smallest Beautiful String is tagged String and Sliding Window on LeetCode.