This is the original question: http://codeforces.net/problemset/problem/486/C

This question uses four keys (up, down, left and right) and can be easily solved by greedy approach in linear time. My question is what if there were only three keys (left, right and up) then how to solve it? Previously, when we found a mismatch between two positions like in (i)th position we have 'b' and in (n-i)th position we have 'c', both of them could be made same using just 1 operation irrespective of the index ((i)th or (n-i)th) where we are performing the operation. But now, 'b' to 'c' will take only 1 operation but 'c' to 'b' will take 25 operations. I think now the question can be solved using DP. But, I am unable to formulate it. Any idea?