Clear the String

Source: CF 1132F

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.

2. Discuss why dynamic programming might be applicable to this problem.

3. Propose a subproblem specification.
   • Start with just enough to answer the problem.
   • If you were to use the operation (deleting a run of a single character), are you left with a part of the string that corresponds to another (smaller) subproblem?
     • If not, you’ll need additional parameters.
     • There is a bit of a trick here!

4. Form a recurrence between your subproblems.

5. Analyse the time complexity of your algorithm, and estimate the running time.
   • If the algorithm is too slow, consider optimisations to reduce the number of subproblems or the work per subproblem.
6. Implement this algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the problem.
   • Run your tests and debug if necessary.
7. Submit your program for judging!
   • Debug if necessary.