Question

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

This question was addressed to me during an online interview.

Question is taken from Minimum Insertions to form a Palindrome topic in chapter Dynamic Programming of Data Structures & Algorithms II

Answer 1

Correct choice is (b) False

The best 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.