Solução Informática - Nivel Iniciante - Semana 4

Solução por Leonardo Paes

Conhecimento prévio necessário:

• Set

Para resolvermos este problema, utilizaremos a estrutura de dados Set do C++.

Inicialmente, ordenamos a string $s$ dada. Então, iremos inserir todos os primeiros $k$ elementos da string no set. Há dois casos a se considerar: todos esses caracteres são o mesmo, ou seja, $set.size() == 1$, ou não.

Se tiver algum caractere que seja diferente, um jeito ótimo de minimizar a string máxima seria utilizando o maior caractere como resposta, ou seja, $s[k-1]$, pois a string que contém esse caractere será a máxima independente dos próximos caracteres utilizados, e colocar mais caracteres nessa string só pioraria a resposta mínima.

Se todos os $k$ primeiros caracteres forem iguais, é ótimo que todas as $k$ strings comecem com esse mesmo caractere. Para o resto da strings, devemos checar se os caracteres restantes são todos iguais. Se eles forem, deveremos distribui-los igualmente entre as $k$ strings, caso contrário, é ótimo colocar todos em uma mesma string.

Confira o código abaixo para melhor entendimento: