The greedy cutter

Question

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:

aaabbccccccbbbaaacccccaabbbaaaaa

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.

---

Example 1:

In:  aaabbccccccbbbaaacccccaabbbaaaaa
Out: 4

Description: If b is fully removed from the bar, iBug could get 4 parts. He can also get 4 parts by removing b and 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

Example 2:

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.

Example 3:

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.

Example 4:

In:  
Out: 0

Description: There's nothing to cut, so zero.

---

There's also some rules that iBug want the programs to obey:

1. iBug dislikes standard loopholes and they are forbidden.

2. 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.

3. 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!

---

Extra

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).

Answer 1

Haskell, 73 71 70 bytes

x#z|z==x=' '|1<2=z
f x=maximum$length(words x):[f$(c#)<$>x|c<-x,c>' ']

^{Thanks to Laikoni for saving 1 byte!}

Try it online!

Answer 2

JavaScript (ES6), 109 90 bytes

f=s=>Math.max((s.match(/\s+/g)||[]).length,...[...s].map(c=>c>` `&&f(s.split(c).join` `)))

<input oninput=o.textContent=/\s/.test(this.value)?``:f(this.value)><pre id=o>0

Somewhat slow on the 123456789 test case. Previous 109-byte answer wasn't limited to !/\s/:

f=
s=>(g=a=>Math.max(a.filter(s=>s).length,...[...a.join``].map(c=>g([].concat(...a.map(s=>s.split(c)))))))([s])

<input oninput=o.textContent=f(this.value)><pre id=o>0

Answer 3

Python 2, 111 93 72 bytes

-21 bytes thanks Kirill L.

f=lambda s:max([len(s.split())]+[f(s.replace(c,' '))for c in s if'/'<c])

Try it online!

Answer 4

Jelly,  13  11 bytes

^{Too many 2-byte instructions}
-2 thanks to Zgarb (use the outer product quick þ >.<)

eþŒPŒr¬S€ṀḢ

A monadic link accepting a list of characters and returning a non-negative integer.

Try it online!

How?

For each subsequence of the input (the sets we may remove, plus redundant equivalents) gets an existence list to identify which are removed then effectively finds how many runs of zeros remain and yields the maximum. The last part works in a slightly odd way since I found it golfier than more naive alternatives - it finds the runs as [element, count] pairs, negates to identify zeros as ones, sums finds the maximum then takes the head (the sum of elements rather than of counts).

eþŒPŒr¬S€ṀḢ - Link: list of characters        e.g. "aabcde"
  ŒP        - power-set - gets all subsequences    ["","a","a","b",...,"bd",...,"aabcde"]
 þ          - outer-product with:
e           -   exists in?                         [[0,0,0,0,0,0],[1,1,0,0,0,0],[1,1,0,0,0,0],[0,0,1,0,0,0],..,[0,0,1,0,1,0]...,[1,1,1,1,1,1]]
    Œr      - run-length encode                    [[[0,6]],[[1,2],[0,4]],[[1,2],[0,4]],[[0,2],[1,1],[0,3]],...,[[0,2],[1,1],[0,1],[1,1],[0,1]],...,[[1,6]]]
      ¬     - NOT                                  [[[1,0]],[[0,0],[1,0]],[[0,0],[1,0]],[[1,0],[0,0],[1,0]],...,[[1,0],[0,0],[1,0],[0,0],[1,0]],...,[[0,0]]]
        €   - for €ach:
       S    -   sum                                [[1,0],[1,0],[1,0],[2,0],...,[3,0],...,[0,0]]
         Ṁ  - maximum                              [3,0]
          Ḣ - head                                 3

Answer 5

Ruby, 98 89 75 64 61 bytes

f=->s{[s.split.size,*s.scan(/\w/).map{|c|f[s.tr c,' ']}].max}

Try it online!

_{^{smaller and slower than before!}}

Basically a port of @Neil's Javascript answer

Ungolfed and annotated

def f(input_string)
    # splits by / +/ by default
    size0 = input_string.split.size
    # an array of all non-space characters in input_string
    characters = input_string.scan(/\w/)
    size1 = characters.map {|i|
        # all letters and digits and _ are "bigger" than /, space isn't
        if i > '/'
            # tr replaces every occurrence of i in input_string with space
            next_string = input_string.tr(i, ' ')
            f(next_string) # recursive call
        else
            0
        end
    }
    # max value between size0 and any element in size1
    return [size0, *size1].max
end

Try it online!

Answer 6

Husk, 12 11 bytes

▲mȯ#€0gM€¹Ṗ

Try it online! This works by brute force and is quite slow. Add u to the right end to make it run faster, without changing the semantics.

Explanation

▲mȯ#€0gM€¹Ṗ  Implicit input, say S = "abddccbdcaab"
          Ṗ  Powerset of S: P = ["","a","b","ab","d","ad"...,"abddccbdcaab"]
 m           Map this function over P:
              Argument is a subsequence, say R = "acc"
       M ¹    Map over S
        €     index of first occurrence in R: [1,0,0,0,2,2,0,0,2,1,1,0]
      g       Group equal elements: [[1],[0,0,0],[2,2],[0,0],[2],[1,1],[0]]
  ȯ#          Count the number of groups
    €0        that contain 0: 3
▲            Take maximum of the results: 4

Answer 7

Perl 5, (older versions), -p -I., 52 49 43 bytes

Old style counting: +3 for -p: 46 bytes (because it must be in a program, it can't be run using -e)

barsplit.pl:

#!/usr/bin/perl -pI.
$G[split]+=s%\S%do$0for s/$&/ /rg%eg;$_=$#G

Run with the string on STDIN:

echo aaabcccdedaaabefda | ./barsplit.pl; echo

Try it online!

The -I. option is there to make this also work on recent perls where by default . is no more in @INC. In older versions of perl that option is not needed. I tested that on an older machine that still had perl 5.20, so the score is based on that (otherwise I should also count the . argument to -I)

Fast version (49 bytes):

#!/usr/bin/perl -pI.
$G[split]+=s%.%$$_++||do$0for s/$&/ /rg%eg;$_=$#G

Answer 8

Wolfram Language (Mathematica), 77 bytes

Max@Table[Tr[1^StringSplit[#,(##|##)..&@@s]],{s,Subsets@Union@Characters@#}]&

Try it online!