Partition string into minimum beautiful substrings

Hash Table String Dynamic Programming Backtracking

53.9% acceptance

Feb 25, 2026

383

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_beautiful_substrings(s: String) -> i32 {
    // Binary representations of powers of 5 up to 2^15
    let powers: Vec<String> = (0..8).map(|k| format!("{:b}", 5i64.pow(k))).collect();
    let n = s.len();
    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0;
    for i in 1..=n {
      for p in &powers {
        let plen = p.len();
        if i >= plen {
          let j = i - plen;
          if dp[j] != i32::MAX && &s[j..i] == p.as_str() {
            dp[i] = dp[i].min(dp[j] + 1);
          }
        }
      }
    }
    if dp[n] == i32::MAX { -1 } else { dp[n] }
  }
}