Skip to content

2767. Partition String Into Minimum Beautiful Substrings 👍

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int minimumBeautifulSubstrings(string s) {
    const int n = s.length();
    // dp[i] := the minimum number of beautiful substrings for the first i chars
    vector<int> dp(n + 1, n + 1);
    dp[0] = 0;

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int minimumBeautifulSubstrings(String s) {
    final int n = s.length();
    // dp[i] := the minimum number of beautiful substrings for the first i chars
    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; // num of s[i - 1..j - 1]
      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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def minimumBeautifulSubstrings(self, s: str) -> int:
    n = len(s)
    # dp[i] := the minimum number of beautiful substrings for the first i chars
    dp = [0] + [n + 1] * n

    for i in range(1, n + 1):
      if s[i - 1] == '0':
        continue
      num = 0  # the number of s[i - 1..j - 1]
      for j in range(i, n + 1):
        num = (num << 1) + int(s[j - 1])
        if self._isPowerOfFive(num):
          dp[j] = min(dp[j], dp[i - 1] + 1)

    return -1 if dp[n] == n + 1 else dp[n]

  def _isPowerOfFive(self, num: int) -> bool:
    while num % 5 == 0:
      num //= 5
    return num == 1