AIBOHP  Aibohphobia
BuggyD suffers from AIBOHPHOBIA  the fear of Palindromes. A palindrome is a string that reads the same forward and backward.
To cure him of this fatal disease, doctors from all over the world discussed his fear and decided to expose him to large number of palindromes. To do this, they decided to play a game with BuggyD. The rules of the game are as follows:
BuggyD has to supply a string S. The doctors have to add or insert characters to the string to make it a palindrome. Characters can be inserted anywhere in the string.
The doctors took this game very lightly and just appended the reverse of S to the end of S, thus making it a palindrome. For example, if S = "fft", the doctors change the string to "ffttff".
Nowadays, BuggyD is cured of the disease (having been exposed to a large number of palindromes), but he still wants to continue the game by his rules. He now asks the doctors to insert the minimum number of characters needed to make S a palindrome. Help the doctors accomplish this task.
For instance, if S = "fft", the doctors should change the string to "tfft", adding only 1 character.
Input
The first line of the input contains an integer t, the number of test cases. t test cases follow.
Each test case consists of one line, the string S. The length of S will be no more than 6100 characters, and S will contain no whitespace characters.
Output
For each test case output one line containing a single integer denoting the minimum number of characters that must be inserted into S to make it a palindrome.
Example
Input: 1 fft Output: 1
hide comments
vaibnak:
20180913 06:36:24
won`t fft be a palindrome in itself i.e ftf, so the answer must be 0. 

mayank_75:
20180905 18:09:29
how is this based on LCS? Can somebody explain.


divyansh_soni:
20180811 20:03:26
Passing string by reference saved me. 

ash_maurya:
20180605 19:37:36
solvable both by bottom up and top down dp. It would not matter as time complexity would be same for both the solutions 

tanmayak99:
20180528 16:44:23
@prashant2018 after passing string as a refernce i am not getting TLE. But why? 

sharmajatin741:
20180521 14:32:39
top down dp is giving TLE


yaswanth desu:
20180414 11:16:37
Lot of people suggesting LCS as solution.


shivam_2296:
20180403 21:24:30
I'm stuck. But, I won't give up. 

prashant2018:
20180326 16:35:14
If using c++ and passing string to recursive function then make sure you pass as a reference or else you will get TLE. 

yeser:
20180325 21:21:41
how it solve dp????

Added by:  Matthew Reeder 
Date:  20061029 
Time limit:  1.940s 
Source limit:  30000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  AlKhawarizm 2006 