O iBug recentemente adquiriu uma barra longa feita de materiais compostos, mas valiosos. A barra é tão longa que o iBug não pode vendê-la facilmente por créditos, então ele quer cortá-la. A barra é feita de materiais tão frágeis e mágicos que, se uma peça for quebrada, todas as partes da barra feitas com o mesmo material também quebrarão, dificultando o corte arbitrário.

O iBug deseja cortar a barra em tantos pedaços quanto possível. Ele também gosta de programas muito curtos e de código-golfe, por isso fez uma análise abstrata de seu problema.

A barra mágica do iBug é representada como uma string (ou uma matriz ou uma sequência de caracteres, se você preferir), assim:

aaabbccccccbbbaaacccccaabbbaaaaa

Cada letra da string representa um material mágico. A barra sempre corresponde ao RegEx ^\w*$, portanto, pode haver até 63 materiais na barra. Uma "parte" é uma sequência consecutiva de caracteres que não são separados por espaços.

O iBug deseja que você escreva um programa que calcule o máximo de partes possível, se zero ou mais conjuntos de caracteres forem totalmente removidos (substituídos por espaços) e informe o número ao iBug.

Exemplo 1:

In:  aaabbccccccbbbaaacccccaabbbaaaaa
Out: 4

Descrição: se bfor totalmente removido da barra, o iBug poderá obter 4 partes. Ele também pode obter 4 partes removendo be c, como mostrado abaixo

aaabbccccccbbbaaacccccaabbbaaaaa  # Original string
aaa  cccccc   aaacccccaa   aaaaa  # Remove 'b'
aaa           aaa     aa   aaaaa  # Remove 'b' and 'c'

E esse é o número máximo de peças que o iBug pode obter dessa barra

Exemplo 2:

In:     111aa___9999____aaa99111__11_a_aa999
Result: 111aa   9999    aaa99111  11 a aa999
Out:    6

Descrição: removendo apenas o sublinhado, o iBug pode obter 6 partes da barra e esse é o máximo.

Exemplo 3:

In:  __________
Out: 1

Descrição: O que? Você quer cortar isso? Só é possível obter 1 parte se você não a cortar.

Exemplo 4:

In:  
Out: 0

Descrição: não há nada para cortar, então zero.

Existem também algumas regras que o iBug deseja que os programas obedeçam:

1. O iBug não gosta de brechas padrão e é proibido.

2. Desde que funcione, ele não precisa ser um programa completo. Também é aceita uma função que recebe entrada de um parâmetro e fornece saída via valor de retorno.

3. Entrada e saída flexíveis são permitidas. Seu programa ou função pode ter uma string, uma matriz de caracteres ou o que você achar mais fácil de lidar. Você pode fornecer a saída imprimindo o número ou retornando-o.

Exemplos de casos de teste (mas não limitados a estes)

aaabbbaaa           = 2
123456789           = 5
AaAaAaAa            = 4
aaabcccdedaaabefda  = 6
________            = 1
(empty)             = 0

Como este é um código de golfe , o programa mais curto (em bytes) em cada idioma vence!

Extra

O iBug aprecia muito se você pode fornecer uma explicação para o seu programa, mesmo que isso não afete sua pontuação (ainda é o comprimento em bytes).

Haskell , 73 71 70 bytes

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

^{Agradecemos a Laikoni por economizar 1 byte!}

Experimente online!

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

Um pouco lento no 123456789caso de teste. A resposta anterior de 109 bytes não se limitou a !/\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

Python 2 , 111 93 72 bytes

-21 bytes graças Kirill L.

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

Experimente online!

Geléia ,  13  11 bytes

^{Muitas instruções de 2 bytes}
-2 graças ao Zgarb (use o produto externo rapidamenteþ>. <)

eþŒPŒr¬S€ṀḢ

Um link monádico que aceita uma lista de caracteres e retorna um número inteiro não negativo.

Experimente online!

Quão?

Para cada subsequência da entrada (os conjuntos que podemos remover, mais os equivalentes redundantes) obtém uma lista de existência para identificar quais são removidos e, efetivamente, descobre quantas execuções de zeros permanecem e produz o máximo. A última parte funciona de uma maneira um pouco estranha, já que eu a achei mais golfista do que as alternativas mais ingênuas - encontra as corridas como [element, count]pares, nega identificar zeros como unidades, somas encontra o máximo e depois pega a cabeça (a soma dos elementos em vez das contagens )

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

Ruby , 98 89 75 64 61 bytes

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

Experimente online!

_{^{menor e mais lento do que antes!}}

Basicamente, uma porta de resposta Javascript do @ Neil

Ungolfed e anotado

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

Experimente online!

Casca , 12 11 bytes

▲mȯ#€0gM€¹Ṗ

Experimente online! Isso funciona com força bruta e é bastante lento. Adicione uà extremidade direita para acelerar a execução, sem alterar a semântica.

Explicação

▲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

Perl 5 , (versões mais antigas), -p -I., 52 49 43 bytes

Contagem de estilo antigo: +3para -p: 46bytes (porque ele deve estar em um programa, não pode ser executado usando -e)

barsplit.pl:

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

Execute com a string em STDIN:

echo aaabcccdedaaabefda | ./barsplit.pl; echo

Experimente online!

A -I.opção existe para fazer isso também funcionar em perls recentes, nos quais, por padrão, .não existe mais @INC. Nas versões mais antigas do perl, essa opção não é necessária. Eu testei isso em uma máquina mais antiga que ainda tinha perl 5.20, então a pontuação é baseada nisso (caso contrário, eu também deveria contar o .argumento -I)

Versão rápida ( 49bytes):

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

Wolfram Language (Mathematica) , 77 bytes

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

Experimente online!