Partition String Into Minimum Beautiful Substrings

Problem Description

Ah, the classic dilemma of partitioning strings! Imagine you’re at a party, and you have to divide your friends into groups based on their favorite snacks. But here’s the catch: each group can only consist of friends who love snacks that are powers of five. Sounds easy, right? Well, welcome to the world of LeetCode, where nothing is as simple as it seems!

In the problem “Partition String Into Minimum Beautiful Substrings,” you are given a binary string. Your task is to partition this string into the minimum number of substrings such that each substring represents a number that is a power of five. If you can’t do it, you must return -1. So, if your string is “101”, you can split it into “1” and “0”, but “0” is not a power of five. Good luck with that!

Code Solution


class Solution {
  public int minimumBeautifulSubstrings(String s) {
    final int n = s.length();
    int[] dp = new int[n + 1];
    Arrays.fill(dp, n + 1);
    dp[0] = 0;

    for (int i = 1; i <= n; ++i) {
      if (s.charAt(i - 1) == '0')
        continue;
      int num = 0;
      for (int j = i; j <= n; ++j) {
        num = (num << 1) + s.charAt(j - 1) - '0';
        if (isPowerOfFive(num))
          dp[j] = Math.min(dp[j], dp[i - 1] + 1);
      }
    }

    return dp[n] == n + 1 ? -1 : dp[n];
  }

  private boolean isPowerOfFive(int num) {
    while (num % 5 == 0)
      num /= 5;
    return num == 1;
  }
}

Approach Explanation

The code uses dynamic programming to solve the problem. It maintains an array dp where dp[i] represents the minimum number of beautiful substrings that can be formed from the first i characters of the string. The algorithm iterates through the string, checking each substring to see if it represents a power of five. If it does, it updates the dp array accordingly.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n²)
Space Complexity	O(n)

Real-World Example

Imagine you’re organizing a game night, and you need to group your friends based on their favorite board games. Each game can only be played by a certain number of players, which are powers of five (1, 5, 25, etc.). You have to figure out how to group them efficiently. Just like in our problem, if you can’t find a suitable grouping, you might end up with a few lonely players.