Решение задачи «сокращение строки»

Я видел различные обсуждения и попытки кода решить проблему "сокращения строк" на сайте интервьюstreet.com, но ни один из них не использует динамическое программирование.

Перечисленная в разделе Динамическое программирование , проблема описана следующим образом:

Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'.

What is the smallest string which can result by applying this operation repeatedly?

Проблема может быть решена с помощью полного перебора -, эффективно создающего дерево всех возможных подстановок:

// this is more or less pseudo code from my head
int GetMinLength(string s)
{
    // solve edge cases
    if (s.Length == 1) return 1;
    if (s.Length == 2) return ReduceIfPossible(s);

    // recursive brute force
    int min = s.Length;
    for (int i = 0; i<s.Length-1; i++)
    {
        if (s[i] != s[i+1])
        {
            var next = GetMinLength(
                  s.Substring(0, i) + 
                  Reduce(s[i], s[i + 1]) +
                  s.Substring(i + 2)
                  );

            if (next < min) min = next;
        }
    }
}

Это явно не работает для большихN(N <= 100), поэтому я пытаюсь разбить его на более мелкие подзадачи, запомнить их и объединить результаты.

Проблема в том, что я не могу определить состояние, которое имело бы "оптимальную подструктуру" , необходимое для применения динамического программирования (или, другими словами, для "объединения" результатов из подзадач -). Минимизация части строки не гарантирует, что окончательная строка действительно будет наименьшим решением.

Каким будет в этом случае подзадача «состояние», которую можно объединить для окончательного решения?