Checking ends of a substring

Question

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;
} 

• saeedn: Maybe you can reduce the memory consumption by a constant factor, but I'm not sure about reducing the space complexity. A simple hint could be: use short int instead of int, because your answer won't go more than length of your string, right?

Answer 1

Things you did well:

• Usage of static.

• Using memset() instead of some for loops for initialization of your int[][].

Things you could improve:

User Experience:

• You don't indicate to the user that they should enter a number first.

  printf("Enter the number of test cases: ");
  

• You don't indicate that the user should enter a string after then enter a number.

  printf("Enter test case string: ");
  

Variables:

• I don't expect dp will ever contain negative numbers:

  static int dp[6101][6101];
  

  You also don't need the full range of int. Using a unsigned short will half your memory usage.

  static unsigned short dp[6101][6101];
  

• Always initialize your variables when you create them.

  int tc = 0;
  

Readability:

• You don't declare what main will return or take in as parameters.

  main()
  

  I know that when the type specifier is missing for what you will return, it defaults to an int. You should still declare it for more readability. Also, whenever you don't take in any parameters, declare them as void.

  int main(void)
  

• Your for loop is hard to follow.

  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;
  

  Braces will help, and will reduce the likelihood of you unintentionally adding bugs in the future.

  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] : fmin(dp[j][k-1], dp[j+1][k])+1;
   }
  }
  

• Don't use the ternary operator for longer statements.

  dp[j][k] = (s[j] == s[k]) ? dp[j+1][k-1] : fmin(dp[j][k-1], dp[j+1][k])+1;
  

  This makes it hard to follow and understand what you are trying to do. Just use the normal if-else statements.

  if (s[j] == s[k]) dp[j][k] = dp[j+1][k-1];
  else dp[j][k] = fmin(dp[j][k-1], dp[j+1][k]) + 1;
  

• Use more space in your code. Let it breathe a bit. But don't go overboard.

• Use more comments to explain your code.

Syntax/Styling:

• You have some magic numbers in your code.

  static int dp[6101][6101];
  

  With the help of macros, we can easily get rid of them.

  #define ARRAYSIZE 6101
  static int dp[ARRAYSIZE][ARRAYSIZE];
  

• Don't use the function min().

  dp[j][k]=(s[j]==s[k])?dp[j+1][k-1]:min(dp[j][k-1],dp[j+1][k])+1;
  

  min() and max() functions are not included in standard C. To make things simple for your code, use the standard math function fmin().

  dp[j][k] = (s[j] == s[k]) ? dp[j+1][k-1] : fmin(dp[j][k-1], dp[j+1][k])+1;
  

• You have an implicit conversion that loses integer precision:

  int len=strlen(s);
  

  You aren't converting your unsigned long that strlen() returns to an int.

  int len = (int) strlen(s);
  

• Use fgets() instead of scanf(). This way we can specify the maximum number of characters to be copied into our string (including the terminating null-character).

  fgets(s, 6101, stdin);
  

• You should always check for superfluous input and get rid of it.

  while (getchar() != '\n');
  

Preprocessor:

• Whenever you include functions such as scanf() and printf() that deal with input or output, you need included the standard I/O header.

  #include <stdio.h> 
  

• Whenever you include functions that deal with strings, there is a good chance you will have to include the string header.

  #include <string.h>
  

• Whenever you include math functions, you need to include the math header.

  #include <math.h>
  

Final Code:

#include <stdio.h>
#include <string.h>
#include <math.h>
#define ARRAYSIZE 6101
static unsigned short dp[ARRAYSIZE][ARRAYSIZE];
char s[ARRAYSIZE] = {0};
int main(void)
{
 int tc = 0;
 printf("Enter the number of test cases: ");
 scanf("%d",&tc);
 while (getchar() != '\n');
 while(tc--)
 {
 printf("Enter test case string: ");
 fgets(s, ARRAYSIZE, stdin);
 int len = (int) strlen(s);
 memset(dp, 0, sizeof dp);
 for(int i=1; i<len; i++)
 {
 for(int j=0, k=i; k<len; k++, j++)
 {
 if (s[j] == s[k]) dp[j][k] = dp[j+1][k-1];
 else dp[j][k] = fmin(dp[j][k-1], dp[j+1][k]) + 1;
 }
 }
 printf("%d\n", dp[0][len-1]);
 }
 return 0;
}

• 200_success: I don't follow your O(n) algorithm at all. But isn't i - 1 >= 0 always true?
• syb0rg: @200_success It turns out my O(n) program was buggy. It has now been removed.