partition-string-into-minimum-beautiful-substrings

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given a binary string <code>s</code>, partition the string into one or more substrings such that each substring is beautiful.

A string is beautiful if:

<ul>
	<li>It doesn&#39;t contain leading zeros.</li>
	<li>It&#39;s the binary representation of a number that is a power of <code>5</code>.</li>
</ul>

Return the minimum number of substrings in such partition. If it is impossible to partition the string <code>s</code> into beautiful substrings,&nbsp;return <code>-1</code>.

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

&nbsp;
Example 1:

<pre>
Input: s = &quot;1011&quot;
Output: 2
Explanation: We can paritition the given string into [&quot;101&quot;, &quot;1&quot;].
- The string &quot;101&quot; does not contain leading zeros and is the binary representation of integer 51 = 5.
- The string &quot;1&quot; 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.
</pre>

Example 2:

<pre>
Input: s = &quot;111&quot;
Output: 3
Explanation: We can paritition the given string into [&quot;1&quot;, &quot;1&quot;, &quot;1&quot;].
- The string &quot;1&quot; 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.
</pre>

Example 3:

<pre>
Input: s = &quot;0&quot;
Output: -1
Explanation: We can not partition the given string into beautiful substrings.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 15</code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

minimumBeautifulSubstrings

Partition String Into Minimum Beautiful Substrings

Partition Array for Maximum Sum

partition-array-for-maximum-sum

分隔数组以得到最大和

Minimum Substring Partition of Equal Character Frequency

minimum-substring-partition-of-equal-character-frequency

分割字符频率相等的最少子字符串

Hash Table

String

Dynamic Programming

Backtracking

给你一个二进制字符串&nbsp;<code>s</code>&nbsp;，你需要将字符串分割成一个或者多个&nbsp;子字符串&nbsp;&nbsp;，使每个子字符串都是 美丽&nbsp;的。

如果一个字符串满足以下条件，我们称它是 美丽&nbsp;的：

<ul>
	<li>它不包含前导 0 。</li>
	<li>它是 <code>5</code>&nbsp;的幂的 二进制&nbsp;表示。</li>
</ul>

请你返回分割后的子字符串的 最少&nbsp;数目。如果无法将字符串&nbsp;<code>s</code>&nbsp;分割成美丽子字符串，请你返回 <code>-1</code>&nbsp;。

子字符串是一个字符串中一段连续的字符序列。

&nbsp;

示例 1：

<pre>输入：s = "1011"
输出：2
解释：我们可以将输入字符串分成 ["101", "1"] 。
- 字符串 "101" 不包含前导 0 ，且它是整数 51 = 5 的二进制表示。
- 字符串 "1" 不包含前导 0 ，且它是整数 50 = 1 的二进制表示。
最少可以将 s 分成 2 个美丽子字符串。
</pre>

示例 2：

<pre>输入：s = "111"
输出：3
解释：我们可以将输入字符串分成 ["1", "1", "1"] 。
- 字符串 "1" 不包含前导 0 ，且它是整数 50 = 1 的二进制表示。
最少可以将 s 分成 3 个美丽子字符串。
</pre>

示例 3：

<pre>输入：s = "0"
输出：-1
解释：无法将给定字符串分成任何美丽子字符串。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 15</code></li>
	<li><code>s[i]</code>&nbsp;要么是&nbsp;<code>'0'</code>&nbsp;要么是&nbsp;<code>'1'</code> 。</li>
</ul>