Data Structure Questions and Answers – Minimum Insertions to form a Palindrome

This set of Data Structure Assessment Questions and Answers focuses on “Minimum Insertions to form a Palindrome”.

1. Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?
a) Greedy algorithm
b) Recursion
c) Dynamic programming
d) Both recursion and dynamic programming
View Answer

Answer: d
Explanation: Dynamic programming and recursion can be used to solve the problem.

2. In which of the following cases the minimum no of insertions to form palindrome is maximum?
a) String of length one
b) String with all same characters
c) Palindromic string
d) Non palindromic string
View Answer

Answer: d
Explanation: In string of length one, string with all same characters and a palindromic string the no of insertions is zero since the strings are already palindromes. To convert a non-palindromic string to a palindromic string, the minimum length of string to be added is 1 which is greater than all the other above cases. Hence the minimum no of insertions to form palindrome is maximum in non-palindromic strings.

3. In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to the length of the string.
a) True
b) False
View Answer

Answer: b
Explanation: In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to length of the string minus one. For example, consider the string “abc”. The string can be converted to “abcba” by inserting “a” and “b”. The number of insertions is two, which is equal to length minus one.

advertisement
advertisement

4. Consider the string “efge”. What is the minimum number of insertions required to make the string a palindrome?
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: b
Explanation: The string can be converted to “efgfe” by inserting “f” or to “egfge” by inserting “g”. Thus, only one insertion is required.

5. Consider the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome?
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: a
Explanation: The given string is already a palindrome. So, no insertions are required.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?
a) Minimum number of jumps problem
b) Longest common subsequence problem
c) Coin change problem
d) Knapsack problems
View Answer

Answer: b
Explanation: A variation of longest common subsequence can be used to solve the minimum number of insertions to form a palindrome problem.

7. Consider the following dynamic programming implementation:

advertisement
#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                 arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return _____________;
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

Which of the following lines should be added to complete the code?
a) arr[len][len]
b) len + arr[len][len]
c) len
d) len – arr[len][len]
View Answer

Answer: d
Explanation: arr[len][len] contains the length of the longest palindromic subsequence. So, len – arr[len][len] gives the minimum number of insertions required to form a palindrome.
advertisement

8. What is the time complexity of the following dynamic programming implementation of the minimum number of insertions to form a palindrome problem?

#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                 arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(mn)
View Answer

Answer: c
Explanation: The time complexity of the above dynamic programming implementation is O(n2).

9. What is the space complexity of the following dynamic programming implementation of the minimum number of insertions to form a palindrome problem?

#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                 arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(mn)
View Answer

Answer: c
Explanation: The space complexity of the above dynamic programming implementation is O(n2).

10. What is the output of the following code?

#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                  arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

a) 1
b) 2
c) 3
d) 4
View Answer

Answer: b
Explanation: The length of the longest palindromic subsequence is 3. So, the output will be 5 – 3 = 2.

11. What is the value stored in arr[2][4] when the following code is executed?

#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                  arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

a) 2
b) 3
c) 4
d) 5
View Answer

Answer: a
Explanation: The value stored in arr[2][4] when the above code is executed is 2.

12. What is the output of the following code?

#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                  arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "efgfe";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

a) 0
b) 2
c) 4
d) 6
View Answer

Answer: a
Explanation: Since the string “efgfe” is already a palindrome, the number of insertions required is 0.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.