複雑性が不明な動的計画アルゴリズム

最近トップコーダーの問題を解くために検索アルゴリズムを書いたが時間的の制限を証明できません。最悪の場合は
choose(26,2)^25なので永遠に動く可能性がありそうです。二つな方法を試して見たが両方が時間的に遅すぎた。The complexity of both of my solutions was worst-case exponential. In the first attempt, the pairs of letters to be removed were generated for each input string in each recursive step. In the second approach, the pairs were generated only for the initial string, and then the list was copied and updated whenever a move was made (the list was passed down the recursive tree. Neither case performed satisfactorily.
恥ずかしいですが実際の正解の複雑性が線形だしアルゴリズムが簡単だった。鍵は模様を意識する事です。
Looking at the examples, a pattern relating the winning letter (or no winning letter) to the number of times the most frequent letter occurs becomes clear. If the most frequent letter occurs x times and all other letters occur k-x times, then the letter is a winner if and only if x>(k-x) (in this case only all other letters can be paired with the winner and, after they are removed, some copies of the winning letter must remain).