Introduction:
We are given a string. We need to find the minimum number of characters we need to add to the string to convert the given string to a palindrome string.
Let us see a few examples.
Input:
“abc”
Output:
2
Explanation:
We need to add ‘b’ and ‘a’ at the end of the String(“abcba”) to make it a palindrome string.
Input:
“aba”
Output:
0
Explanation:
The input string is already a palindrome string. Hence, 0 insertions are needed to make it Palindrome.
Approach 1:
We can use a recursive approach here. We will keep two pointers ‘i’ and ‘j’. ‘i’ will be at the 0th index, and the ‘j’ pointer will be at the (N - 1)th index.
If the characters at the ‘i’ and ‘j’ positions are equal, the answer would be calculated by calling the recursive function (i + 1, j - 1).
Also, we will call the recursive function for fun(i + 1, j) + 1 and fun(i, j - 1) + 1. We are adding 1 to the answer of both the recursive calls because we need to add one character to balance the ‘i’th or ‘j’th character. In the end, we will return the minimum among them.
Refer to the below implementation of the above approach.
class Main { /* Recursive function to find the minimum number of insertions to make The string palindrome */ static int findMinimumInsertions(char str[], int l, int h) { // Base Cases if (l > h) { return Integer.MAX_VALUE; } if (l == h) { return 0; } if (l == h - 1) { return (str[l] == str[h]) ? 0 : 1; } /* Check if the first and last characters are the same. On the basis of this comparison result, decide which subproblem(s) we need to call */ if((str[l] == str[h])) return findMinimumInsertions(str, l + 1, h - 1); return (Integer.min(findMinimumInsertions(str, l, h - 1), findMinimumInsertions(str, l + 1, h)) + 1); } public static void main(String args[]) { String str= "abc"; System.out.println(findMinimumInsertions(str.toCharArray(), 0, str.length()-1)); } } |
Time Complexity: The time complexity of the above approach is O(2 ^ N). In the worst case, we will be trying both the cases of either incrementing the ‘i’ pointer or decrementing the ‘j’ pointer.
Space Complexity: The space complexity of the above approach is O(1) because we are using the constant auxiliary space.