Answers for "minimum number of deletions to make a string palindrome"

minimum number of deletions to make a string palindrome

//Code by @soumyadeepp : Soumyadeep Ghosh

//A very Simple DP problem. Just find the length of the Longest common subsequence 
//of the string and its reverse. Now subtract this length from the actual length
//of the substring. That's it.

#include <bits/stdc++.h>

using namespace std;

int lps(string s)
{
	string r = s;
	reverse(r.begin(),r.end());
	int sz1 = s.size();
	int dp[sz1+1][sz1+1];
	
	for(int i = 0 ; i <= sz1 ; i++)
	{
		dp[0][i] = 0;
		dp[i][0] = 0;
	}
	for(int i = 1; i <= sz1; i++)
	{
		for(int j = 1; j <= sz1 ; j++)
		{
			if(s[i-1] == r[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[sz1][sz1];
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		string s;
		cin>>s;
		int ans = s.size() - lps(s);
		cout<<ans<<endl;
	}
}