MediumNo. 2767
Partition String Into Minimum Beautiful Substrings — LeetCode 2767 Python Solution
- Pattern
- Backtracking
- Topics
- Hash Table, String, Dynamic Programming, Backtracking
- Reading time
- 4 min
- Source
- leetcode.com
The problem
Given a binary string s, partition the string into one or more substrings such that each substring is beautiful. A string is beautiful if: It doesn't contain leading zeros.
Example
- Input
- s = "1011"
- Output
- 2
- Explanation
- We can paritition the given string into ["101", "1"].
Python solution
class Solution:
def minimumBeautifulSubstrings(self, s: str) -> int:
@cache
def dfs(i: int) -> int:
if i >= n:
return 0
if s[i] == "0":
return inf
x = 0
ans = inf
for j in range(i, n):
x = x << 1 | int(s[j])
if x in ss:
ans = min(ans, 1 + dfs(j + 1))
return ans
n = len(s)
x = 1
ss = {x}
for i in range(n):
x *= 5
ss.add(x)
ans = dfs(0)
return -1 if ans == inf else ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 2767. Partition String Into Minimum Beautiful Substrings is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0140 | Word Break II | Hard |
| 0691 | Stickers to Spell Word | Hard |
| 1255 | Maximum Score Words Formed by Letters | Hard |
| 0017 | Letter Combinations of a Phone Number | Medium |
| 0126 | Word Ladder II | Hard |
| 0139 | Word Break | Medium |
Frequently asked questions
- How hard is LeetCode 2767. Partition String Into Minimum Beautiful Substrings?
LeetCode 2767. Partition String Into Minimum Beautiful Substrings is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2767. Partition String Into Minimum Beautiful Substrings?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2767. Partition String Into Minimum Beautiful Substrings?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2767. Partition String Into Minimum Beautiful Substrings cover?
LeetCode 2767. Partition String Into Minimum Beautiful Substrings is tagged Hash Table, String, Dynamic Programming and Backtracking on LeetCode.