Algorithms
Medium
2767
2883
Partition String Into Minimum Beautiful Substrings
partition-string-into-minimum-beautiful-substrings
"""
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.

Example 1:

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

Example 2:

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

Example 3:

Input: s = "0"
Output: -1
Explanation: We can not partition the given string into beautiful substrings.


Constraints:

 * 1 <= s.length <= 15
 * s[i] is either '0' or '1'.
"""
class Solution:
    def minimumBeautifulSubstrings(self, s: str) -> int:
        
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.

Example 1:

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

Example 2:

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

Example 3:

Input: s = "0"
Output: -1
Explanation: We can not partition the given string into beautiful substrings.


Constraints:

 * 1 <= s.length <= 15
 * s[i] is either '0' or '1'.


Please complete the code below to solve above prblem:
```python
class Solution:
    def minimumBeautifulSubstrings(self, s: str) -> int:
        
```

my_solution = Solution()

test_input = { "s": "1011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 2

test_input = { "s": "111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 3

test_input = { "s": "0" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == -1

test_input = { "s": "100111000110111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 4

test_input = { "s": "100111000111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 3

test_input = { "s": "1001110001111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 4

test_input = { "s": "100111000111101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 4

test_input = { "s": "10110011100011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 3

test_input = { "s": "101101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 2

test_input = { "s": "101101101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 3

test_input = { "s": "101101101101101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "1011011011101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "10110110111011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "101101101111001" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "1011011011111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "101101110011101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "10110111001111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "1011011101101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "101101110110111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "101101110111011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "1011011101111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "101101110111101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "10110111011111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 8

test_input = { "s": "101101111001101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "10110111101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "10110111101101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "101101111011011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "101101111011101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "10110111101111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 8

test_input = { "s": "101101111011111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 9

test_input = { "s": "1011011111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "1011011111001" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "101101111101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "1011011111011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "10110111110111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 8

test_input = { "s": "10110111111001" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "101101111110011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "10110111111011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 4

test_input = { "s": "101101111110111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "101101111111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 8

test_input = { "s": "101101111111101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "101110011011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 4

test_input = { "s": "10111001101101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 4

test_input = { "s": "101110011011111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "1011100111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 4

test_input = { "s": "10111001110001" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 3

test_input = { "s": "10111001110011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 4

test_input = { "s": "1011100111011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "10111001110111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "10111001111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "10111001111001" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 4

test_input = { "s": "1011100111101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "101110011110111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "101110011111001" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "10111001111101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "101110011111011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "1011100111111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "10111001111111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 8

test_input = { "s": "1011101101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 4

test_input = { "s": "10111011011011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "101110110111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "101110110111011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "1011101101111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "101110111001101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "101110111001111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "10111011101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "10111011101111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 8

test_input = { "s": "101110111011111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 9

test_input = { "s": "1011101111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "1011101111001" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "10111011110011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "101110111101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "1011101111011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "10111011111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "10111011111001" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "10111011111011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 8

test_input = { "s": "101110111110111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 9

test_input = { "s": "101110111111001" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "101110111111011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "101110111111101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "10111011111111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 10

test_input = { "s": "101110111111111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 11

test_input = { "s": "101111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 4

test_input = { "s": "101111001" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 3

test_input = { "s": "1011110011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 4

test_input = { "s": "10111100110111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "101111001110001" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 4

test_input = { "s": "101111001111101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "10111100111111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 8

test_input = { "s": "101111011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "10111101101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "101111011011" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "10111101101101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 6

test_input = { "s": "1011110110111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "1011110111101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 7

test_input = { "s": "101111011110111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 9

test_input = { "s": "101111011111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 8

test_input = { "s": "1011110111111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 9

test_input = { "s": "101111011111101" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 5

test_input = { "s": "10111101111111" }
assert my_solution.minimumBeautifulSubstrings(**test_input) == 10