iBug recently got a long bar made of composite, yet valuable materials. The bar is so long that iBug can't easily sell it for credits, so he wants to cut it. The bar is made of such fragile and magic materials that, if a part is broken, all parts of the bar made of the same material will break, too, making it hard to cut arbitrarily.
iBug wants to cut the bar into as many pieces as possible. He also loves very short programs and code-golfing, so he made an abstract analysis of his problem.
iBug's magic bar is represented as a string (or an array or a sequence of characters if you prefer), like this:
Each letter in the string represents one magic material. The bar always matches the RegEx
^\w*$, so there may be up to 63 materials in the bar. A "part" is a consecutive sequence of any characters that are not separated by spaces.
iBug wants you to write a program that calculates the maximum parts that he could get, if zero or more character sets are fully removed (replaced by spaces), and tell iBug that number.
In: aaabbccccccbbbaaacccccaabbbaaaaa Out: 4
b is fully removed from the bar, iBug could get 4 parts. He can also get 4 parts by removing
c, as is shown below
aaabbccccccbbbaaacccccaabbbaaaaa # Original string aaa cccccc aaacccccaa aaaaa # Remove 'b' aaa aaa aa aaaaa # Remove 'b' and 'c'
And that's the maximum number of parts iBug can get from this bar
In: 111aa___9999____aaa99111__11_a_aa999 Result: 111aa 9999 aaa99111 11 a aa999 Out: 6
Description: By removing only the underscore, iBug can get 6 parts from the bar and that's the maximum.
In: __________ Out: 1
Description: What? You wanna cut this? It's only possible to get 1 part if you don't cut it at all.
In: Out: 0
Description: There's nothing to cut, so zero.
There's also some rules that iBug want the programs to obey:
iBug dislikes standard loopholes and they are forbidden.
As long as it works, it need not be a full program. A function that takes input from a parameter and gives output via return value is also accepted.
Flexible input and output are allowed. Your program or function can take a string, or an array of characters, or whatever you find easiest to deal with. You can give the output by printing the number or returning it.
Sample test cases (but not limited to these)
aaabbbaaa = 2 123456789 = 5 AaAaAaAa = 4 aaabcccdedaaabefda = 6 ________ = 1 (empty) = 0
Since this is a code-golf, the shortest program (in bytes) in each language wins!
iBug highly appreciates if you can provide an explanation for your program, even though it does not affect your scoring (it's still length in bytes).