#2767

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Partition String Into Minimum Beautiful Substrings

Partition a binary string into the fewest beautiful substrings using state transition dynamic programming and careful substring validation.

hash table string dynamic programming backtracking

Problem Statement

Given a binary string s, partition it into one or more substrings such that each substring represents a positive integer that is a power of 5 and contains no leading zeros.

Return the minimum number of substrings in such a partition. If it is impossible to split s into beautiful substrings, return -1. Each substring must strictly follow the beautiful condition to be counted.

Examples

Example 1

Input: s = "1011"

Output: 2

We can paritition the given string into ["101", "1"].

The string "101" does not contain leading zeros and is the binary representation of integer 51 = 5.
The string "1" does not contain leading zeros and is the binary representation of integer 50 = 1. It can be shown that 2 is the minimum number of beautiful substrings that s can be partitioned into.

Example 2

Input: s = "111"

Output: 3

We can paritition the given string into ["1", "1", "1"].

The string "1" does not contain leading zeros and is the binary representation of integer 50 = 1. It can be shown that 3 is the minimum number of beautiful substrings that s can be partitioned into.

Example 3

Input: s = "0"

Output: -1

We can not partition the given string into beautiful substrings.

Constraints

1 <= s.length <= 15
s[i] is either '0' or '1'.

Solution Approach

Dynamic Programming Setup

Define a DP array where dp[i] represents the minimum number of beautiful substrings for the prefix s[0..i]. Initialize dp[0..n] with infinity, and dp[-1] = 0 as the base case.

Substring Validation

For each ending index i, iterate all starting indices j <= i. Convert s[j..i] to a decimal integer, skip if it has leading zeros, and check if it is a power of 5 by repeatedly dividing by 5 until 1 is reached. If valid, update dp[i] = min(dp[i], dp[j-1] + 1).

Result Extraction

After filling dp, check dp[n-1]. If it remains infinity, return -1 as no valid partition exists. Otherwise, dp[n-1] gives the minimum number of beautiful substrings. This approach captures state transitions efficiently and avoids redundant checks.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2 * log(maxValue)) due to iterating all substrings and checking power-of-5 condition, where n is string length. Space complexity is O(n) for the DP array.

What Interviewers Usually Probe

Recognize that simple greedy splitting often fails due to overlapping substrings and multiple partition paths.
Check for leading zeros carefully as they invalidate the beautiful substring condition.
Expect candidates to explain how DP state transitions prevent redundant recalculation of overlapping prefixes.

Common Pitfalls or Variants

Common pitfalls

Assuming all substrings starting with 1 are valid powers of 5 without proper division check.
Ignoring substrings with leading zeros which breaks the beautiful substring rule.
Not considering all possible partition endpoints leading to suboptimal counts.

Follow-up variants

Partition into minimum substrings that are powers of 3 instead of 5.
Count all possible partitions rather than only minimum ones.
Restrict substrings to a maximum length and still check for power-of-5.

FAQ

How does 'Partition String Into Minimum Beautiful Substrings' use dynamic programming?

DP tracks the minimum partitions for each prefix. By validating every substring ending at each index and updating the state, it ensures the fewest beautiful substrings.

What is a beautiful substring in this problem?

A beautiful substring is a binary string representing a positive integer that is a power of 5 and has no leading zeros.

Why can't greedy splitting work for this problem?

Greedy splitting may miss longer substrings that reduce the total count. Only DP guarantees checking all overlapping partitions to find the minimum.

What is the best way to check if a number is a power of 5?

Divide the number by 5 repeatedly while it is divisible. If you reach 1, it is a power of 5; otherwise, it is not.

What are common mistakes when implementing this solution?

Ignoring leading zeros, failing to check all substring endpoints, and assuming any '1' starting substring is automatically beautiful.

terminal

Solution

Solution 1: Memoization Search

Since the problem requires us to judge whether a string is the binary representation of a power of $5$, we might as well first preprocess all the powers of $5$ and record them in a hash table $ss$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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 ans

Continue Practicing

#2707 extra characters in a string #2606 find the substring with maximum cost #2597 the number of beautiful subsets