Shortest and Lexicographically Smallest Beautiful String — LeetCode 2904 Python Solution
MediumStringSliding Window
- Problem
- #2904
- Pattern
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(n^3) |
| Space | O(n) auxiliary |
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
LeetCode 1044Longest Duplicate SubstringHardLeetCode 1208Get Equal Substrings Within BudgetMediumLeetCode 1234Replace the Substring for Balanced StringMediumLeetCode 1456Maximum Number of Vowels in a Substring of Given LengthMediumLeetCode 1839Longest Substring Of All Vowels in OrderMediumLeetCode 1871Jump Game VIIMedium
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(n^3).
- 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.