Some information about task PALIN A good method to solve this problem is to determine the length L of a longest common subsequence (maximal matching) for the input and its reverse. The answer then is N - L. An alternative approach is to match a prefix of the string with the reverse of a postfix. The length of a longest common subsequence can be determined by dynamic programming. A triangular table can be constructed, of which only two rows need to be stored. The complexity is then O(N) space and O(N^2) time. Note that constructing a witness (indicating where which characters have to be inserted to make a palindrome) is computationally more involved and is not asked. For special inputs, other simpler methods may apply. The 10 test cases have the following characteristics: Case # N D A Kind of data ------ ---- -- ---- ------------ 1 62 62 61 Each allowed character exactly once 2 4960 62 4801 80 repetitions of case #1 3 5000 1 0 '9'^5000 4 5000 2 2500 'A'^2500 ++ 'z'^2500 5 5000 2 1 'PC'^2500 6 100 48 79 Random 7 3 2 1 'FFT' 8 5000 2 919 Random with only characters 'O' and 'K' 9 4999 10 2628 Random with only digits 10 4999 20 88 'W'^4999 randomly perturbed in few places where N = length of the string (input) D = number of distinct characters in input string A = correct answer