Partition String Into Minimum Beautiful Substrings

Partition String Into Minimum Beautiful Substrings - 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.
It's the binary representation of a number that is a power of 5.

Return the minimum number of substrings in such partition. If it is impossible to partition the string s into beautiful substrings, return -1.

A substring is a contiguous sequence of characters in a string.

Input & Output

Example 1 — Valid Partition

$ Input: s = "1011"

› Output: 2

💡 Note: The string "1011" can be partitioned as "101" + "1". Both "101" (binary for 5¹=5) and "1" (binary for 5⁰=1) are powers of 5, so minimum partitions = 2.

Example 2 — No Valid Partition

$ Input: s = "111"

› Output: -1

💡 Note: No way to partition "111" into beautiful substrings. "1" is valid but "11" is not a power of 5 (binary 11 = decimal 3). "111" (decimal 7) is also not a power of 5.

Example 3 — Single Character

$ Input: s = "1"

› Output: 1

💡 Note: The string "1" itself is beautiful (binary representation of 5⁰=1), so only 1 partition needed.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string that needs to be partitioned

Identify

Find valid power-of-5 substrings without leading zeros

Partition

Return minimum number of beautiful substrings

Key Takeaway

🎯 Key Insight: Precompute power-of-5 binary patterns and use DP to find minimum partitions

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is to precompute all valid power-of-5 binary representations and use dynamic programming to find minimum partitions. The optimal approach uses memoized backtracking or bottom-up DP. Time: O(n³), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Backtracking	O(n³)	O(n)	Add memoization to avoid recalculating the same subproblems
Backtracking with Recursion	O(2ⁿ)	O(n)	Try all possible partitions recursively and find the minimum
Dynamic Programming (Bottom-Up)	O(n³)	O(n)	Build solution iteratively from smaller subproblems

Memoized Backtracking — Algorithm Steps

Precompute all valid power-of-5 binary strings
Use recursion with memoization cache
For each position, try all valid substrings
Cache and reuse results for each starting position

Visualization

Tap to expand

Step-by-Step Walkthrough

First Calculation

Calculate result for position and store in cache

Cache Hit

When same position encountered again, return cached result

Optimized

Significant speedup by avoiding repeated work

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

char powersOf5[20][20];
int powerCount = 0;
int memo[16]; // Cache for memoization
int memoSet[16]; // Track which positions are memoized

void generatePowersOf5(int maxLen) {
    long long power = 1;
    powerCount = 0;
    while (powerCount < 15) {
        char binary[20] = {0};
        long long temp = power;
        int pos = 0;
        while (temp > 0) {
            binary[pos++] = '0' + (temp % 2);
            temp /= 2;
        }
        for (int i = 0; i < pos/2; i++) {
            char t = binary[i];
            binary[i] = binary[pos-1-i];
            binary[pos-1-i] = t;
        }
        binary[pos] = '\0';
        
        if (strlen(binary) <= maxLen) {
            strcpy(powersOf5[powerCount++], binary);
        }
        if (power > LLONG_MAX/5) break;
        power *= 5;
    }
}

int isBeautiful(char* substring) {
    if (substring[0] == '0') return 0;
    for (int i = 0; i < powerCount; i++) {
        if (strcmp(substring, powersOf5[i]) == 0) {
            return 1;
        }
    }
    return 0;
}

int backtrack(char* s, int start, int len) {
    if (start == len) {
        return 0;
    }
    
    if (memoSet[start]) {
        return memo[start];
    }
    
    int minPartitions = INT_MAX;
    for (int end = start + 1; end <= len; end++) {
        char substring[20] = {0};
        strncpy(substring, s + start, end - start);
        substring[end - start] = '\0';
        
        if (isBeautiful(substring)) {
            int result = backtrack(s, end, len);
            if (result != -1 && result < minPartitions - 1) {
                minPartitions = 1 + result;
            }
        }
    }
    
    memo[start] = minPartitions == INT_MAX ? -1 : minPartitions;
    memoSet[start] = 1;
    return memo[start];
}

int solution(char* s) {
    memset(memoSet, 0, sizeof(memoSet));
    generatePowersOf5(strlen(s));
    return backtrack(s, 0, strlen(s));
}

int main() {
    char s[16];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Each position calculated once (n), trying all substrings (n), checking validity (n)

⚠ Quadratic Growth

Space Complexity

O(n)

Memoization cache stores result for each of n positions

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler