Insert Minimum To Make Palindrome Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/min-insertion-palindrome

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a string s, find the minimum number of characters you need to insert at the beginning in order to make the string a palindrome.

Naive Approach

The simple solution is to find the maximum palindromic string starting from the index 0. The answer will be 

n - length of maximum palindromic string since the remaining elements after the palindromic string must be added before the palindromic string to make the string s a palindrome.

• Run two nested loops, the outer loop from last = n to last = 1 and the inner loop from 0 to last to check if the current substring is palindromic.
• As soon as a palindromic string is found return n - last as answer.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int minCharactersToBeInserted (string A) {
    int n = A.size();
	for (int last = n; last > 0; last--) {
		int isPalindrome = 1;
		for (int i = 0; i < last / 2; i++) {
			if (A[i] != A[last - i - 1]) {
				isPalindrome = 0;
				break;
			}
		}
		if (isPalindrome) {
			return n - last;
		}
	}
}

Java

class Solution {
	int minCharactersToBeInserted (String A) {
	    int n = A.length();
		for (int last = n; last > 0; last--) {
			int isPalindrome = 1;
			for (int i = 0; i < last / 2; i++) {
				if (A.charAt(i) != A.charAt(last - i - 1)) {
					isPalindrome = 0;
					break;
				}
			}
			if (isPalindrome == 1) {
				return n - last;
			}
		}
		return 0;
	}
}

Optimal Approach

The problem can be solved more efficiently by using the concept of LPS which is used in the Knuth Morris Pratt (KMP) Algorithm. LPS of a string is the longest proper prefix which is also a suffix.

Example:

String: AABCDAA

Proper prefixes: A,AA,AAB,AABC,AABCD and AABCDA.

LPS of the above-given string is AA.

To solve this problem we will create an lps array where lps[i] denotes the length of the lps of substring s[0…i].

• Here, the idea is to reverse the given string and append it in the original string separated by a special character(say ‘#’) to find the maximum palindromic string.
• Now traverse the string and find the lps array of the string.
• Only the last element of the lps array is useful to us as it shows the largest suffix of the reversed string that is equal to the prefix of the original string (i.e it gives us the maximum length substring which satisfies the palindrome property).
• The number of elements required to be added to make the string palindrome will be the length of the original array minus the value of the last element of the lps array.

Example:

String S = ACBABCADE

S after appending its reverse = ACBABCADE#EDACBABCA

LPS array of the string = {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7}

Answer = n - last element of lps array = 9 - 7 = 2

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

 int minCharactersToBeInserted (string s) {
	string rev = s;
	reverse (rev.begin(), rev.end());
	s += '#';
	s += rev;
	int n = s.size(), lps[n], palindromeLength = 0;
	lps[0] = 0;
	int i = 1;
	while(i < n) {
		if (s[i] == s[palindromeLength]) {
			palindromeLength++;
			lps[i++] = palindromeLength;
		} else {
			if (palindromeLength == 0)
				lps[i++] = 0;
			else
				palindromeLength = lps[palindromeLength - 1];
		}
	}
	int ans = n / 2 - lps[n - 1];
	return ans;
}

Java

class Solution {
	int minCharactersToBeInserted (String s) {
		StringBuilder rev = new StringBuilder();
		rev.append(s);
		rev.reverse();
		s += '#';
		s += rev;
		int n = s.length(), palindromeLength = 0;
		int[] lps = new int[n];
		lps[0] = 0;
		int i = 1;
		while(i < n) {
			if (s.charAt(i) == s.charAt(palindromeLength)) {
				palindromeLength++;
				lps[i++] = palindromeLength;
			} else {
				if (palindromeLength == 0)
					lps[i++] = 0;
				else
					palindromeLength = lps[palindromeLength - 1];
			}
		}
		int ans = n / 2 - lps[n - 1];
		return ans;
	}
}