Partition String Into Minimum Beautiful Substrings — LeetCode 2767 Python Solution
MediumHash TableStringDynamic ProgrammingBacktracking
- Problem
- #2767
- Pattern
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
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
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.