mininsert-palindrome

You are given a string of characters, or numbers. Find the minimum number of characters to be inserted into the string in order to obtain a palindrome. 
A palindrome is a word, phrase, number, or other sequence of symbols or elements that reads the same forward or reversed. 

For example, the string abcbd can be transformed into a palindrome ("dabcbad" or "adbcbda"). However, inserting fewer than 2 characters will not produce a palindrome.

Input Format:

First line contains test cases and second line contains an integer 'n' specifying the length of the string, where 3 ≤ n ≤ 20
Second line contains a string of length n. 

Note:

Upper-case and lower-case characters are considered as different. Elements of the string are either English alphabets or numerals.

Output Format:

One line containing the minimum number of insertions required to make the string a palindrome

SAMPLE INPUT
2
5
nitin
7
aabbaab

SAMPLE OUTPUT
0
1

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def min_insert(s):
	if len(s) == 1 or len(s) == 0:
		return 0
	return min_insert(s[1:-1]) if s[0] == s[-1] else 1 + min(min_insert(s[:-1]), min_insert(s[1:]))

T = eval(input())
for t in range(T):
	N = eval(input())
	s = input()
	print(min_insert(s))


#finding the longest common subsequence of s and rev(s)
def longestSeq(s):
	dp = [[0 for i in range(len(s)+1)] for i in range(len(s)+1)]
	rev = s[::-1]
	for i in range(len(s)+1):
		for j in range(len(rev)+1):
			if(i==0 or j==0):
				dp[i][j] = 0
			elif(s[i-1]==rev[j-1]):
				dp[i][j] = dp[i-1][j-1] +1
			else:
				dp[i][j] = max(dp[i-1][j],dp[i][j-1])
	return dp[len(s)][len(s)]
for _ in range(eval(input())):
	n=int(eval(input()))
	x=input()
	print(len(x)-longestSeq(x))




#!/usr/bin/python
# -*- encoding: utf-8 -*-
# pylint: disable=invalid-name,missing-docstring,bad-builtin
from sys import stdin


def lcs(a, b):
	lengths = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
	# row 0 and column 0 are initialized to 0 already
	for i, x in enumerate(a):
		for j, y in enumerate(b):
			if x == y:
				lengths[i+1][j+1] = lengths[i][j] + 1
			else:
				lengths[i+1][j+1] = \
					max(lengths[i+1][j], lengths[i][j+1])
	return lengths[-1][-1]

def main():
	dstream = iter(stdin.read().split())
	for _ in range(int(next(dstream))):
		n, word = int(next(dstream)), next(dstream)
		print(n - lcs(word, word[::-1]))

main()