Остановился на тесте кодирования - проблема раздражает - пожалуйста, предложения

Question

Позвольте мне начать с того, что я провалил это испытание - оно уже закончилось, я не выполнил его, не получил работу - так что не говорите мне, что я обманываю, прося о помощи. У меня было 90 минут, чтобы решить эту проблему.

Кстати, если кто-то знает, как называется этот общий класс проблем, дайте мне знать.

Вот, насколько я могу вспомнить , вопрос.

Дана случайная последовательность символов из набора {'a', 'b'}. Создайте 3 подмножества из последовательности, например: с учетом aaaa подмножества:

1. aa-aa
2. a-aa-a
3. aa-aa

Каждое подмножество должно иметь по крайней мере 1 'a'. Если последовательность имеет ноль 'a', то перечислите возможные группы b (как выше с 4 'a') Если последовательность имеет только 1 или 2 ' a ', то не обрабатывать (это, конечно, тривиально для проверки)

так, вот немного более сложный пример:

Учитывая "babbaaba"

подмножества будут:

1. ba-bbaab-a
2. bab-baab-a
3. babb-aab-a
4. babba-ab- а
5. ба-бба-ба
6. ба-бба-аба
7. баб-ба-ба
8. баб-ба-аба и т. c. .. (извините, неполно, не надо вас утомлять)

Я не могу придумать хороший способ решить эту проблему, я снова и снова просматривал свой (ручной) процесс, и на самом деле не вижу никакого алгоритма, возникающего из этого.

Был лимит на максимальный размер набора, возможно, 10 000 символов. Предположительно, чтобы указать, что использование рекурсии не будет проблемой.

Answer 1

Пусть длина строки n. Составьте список / массив длиной n и заполните его счетчиками «a» от начала до i-й позиции. Общее количество «а» составляет na. (можно считать "на лету" без сохранения значений).

b a b b a a b a  
0 1 1 1 2 3 3 4   na=4

Вы можете разместить первый разделитель в любом месте между первым 1 и первым na-1

0 1 1 1 2 3 3 4
   ^ ^ ^ ^

Пусть первый делитель идет после count C. Вы можете разместить второй разделитель в любом месте после первого C+1 и первого na.

0 1 1 1 2 3 3 4
     ^             C=1
         ^ ^ ^     possible second dividers

0 1 1 1 2 3 3 4
         ^         C=2
           ^ ^     possible second dividers

Таким образом, вы можете сгенерировать все допустимые разделы с двумя вложенными циклами for.