I was doing this particular problem AIBOHP and used a dp approach based on checking the ends of a substring of length i starting from 1. Although my time complexity is fine at O(n^2) but space is taking too much because of which I am getting RTE if I am declaring it dynamically or TLE if I am declaring it as global static which needs to be reduced because the dp size can be 6100*6100 . Any suggestions how to optimize my below code for this purpose .
The problem statement is:
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.
My code:
static int dp[6101][6101];
main()
{
int tc;
scanf("%d",&tc);
while(tc--)
{
char s[6102];
scanf("%s",s);
int len=strlen(s);
memset(dp,0,sizeof dp);
for(int i=1;i<len;i++)
for(int j=0,k=i;k<len;k++,j++)
dp[j][k]=(s[j]==s[k])?dp[j+1][k-1]:min(dp[j][k-1],dp[j+1][k])+1;
printf("%d\n",dp[0][len-1]);
}
return 0;
}
short int
instead ofint
, because your answer won't go more than length of your string, right? \$\endgroup\$