Minimum characters to be added at front to make string palindrome in Java
Given a string named strg. Our objective is to find how many characters must be added to the beginning of the string to make it a palindrome. A palindrome is a set of characters that reads the same forward and backward. So, the goal is to identify the minimum set of characters needed to create a symmetrical sequence that has palindrome properties.
Example 1:
Input: Strg = “CAT”
Output: 2
Explanation: By adding 2 characters i.e., TA at the beginning of the string, we can make it as TACAT, which is a palindrome.
Example 2:
Input: strg = “BIBEGDF”
Output: 4
Explanation: The 4 characters i.e, FDGE are required to make the string as palindrome, i.e., FDGEBIBEGDF
Example 3:
Input: Strg = “DDEFEDDD”
Output: 1
Explanation: only 1 D is required to add at the beginning of the string, then we get palindrome as DDDEFEDDD.
Navie Approach:
The following are the steps to solve the problem.
Step 1: Create a variable called foundFlag to record whether a palindrome is found or not and a counter named cunt to record the number of characters inserted at the front.
Step 2: Iterate through the input string with a loop until it is empty.
Step 3: Check whether the current string is a palindrome.
Step 3.1: If the string is a palindrome, set the flag to true and exit the loop.
Step 3.2: If the string is not a palindrome, increment the counter named cunt and remove the last character from it.
Step 4: After execution of the loop, if a palindrome is found, output the number of characters appended at the front.
Step 5: If a palindrome cannot be found, indicate that the supplied string and the new characters are not able to form a palindrome.
FileName: MinCharForStringToPalindrome.java
public class MinCharForStringToPalindrome { // method to verify if a given string is a palindrome static boolean VerifyForPalindrome(String strg) { int ltr = strg.length(); for (int i = 0, j = ltr - 1; i <= j; i++, j--) { if (strg.charAt(i) != strg.charAt(j)) { return false; } } return true; } // main method public static void main(String[] args) { // provide input values String strg = "BIBEGDF"; int cunt = 0; int flag = 0; // iterate until the string becomes empty while (strg.length() > 0) { if (VerifyForPalindrome(strg)) { flag = 1; // to indicate palindrome is found break; } else { cunt++; // removing the last character from the string strg = strg.substring(0, strg.length() - 1); } } if (flag == 1) { System.out.println("The minimum number of characters required to make palindrome are: "); System.out.println(cunt); } } }
Output:
The minimum number of characters required to make palindrome are: 4
Complexity analysis: The time complexity is O(n) because the VerifyForPalindrome method iterates through a string and compares characters until the midpoint. And the while loop takes O(N^2) time until the string becomes empty. Therefore, the overall time complexity is O(n^2) where, n is the length of the input string. The space complexity is O(1), which means constant space is required, irrespective of input size.
Approach: Using Two Pointers
Here is an another way to solve the problem, observe the below steps.
Step 1: Create a variable named n that stores the length of the string, two pointer variables named startPtr and endPtr for the start and end points of the String, and a variable named resl to hold the result.
Step 2: Iterate through startPtr and endPtr using a while loop.
Step 3: Check whether the characters at startPtr and endPtr are equal.
Step 3.1: If they are equal, shift both pointers to the center of the string.
Step 3.2: If they are not equal, increment the result and adjust the pointers in order to try creating a palindrome.
Step 4: Finally, return the value of resl variable, which represents the minimum number of characters needed to make the string a palindrome.
FileName: MinCharForStringToPalindrome.java
public class MinCharForStringToPalindrome { // method to calculate the minimum number of characters required to make the input string as palindrome public int minCharReqToAdd(String stng) { int n = stng.length(); int startPtr = 0; // Starting pointer of the string int endPtr = n - 1; // ending pointer of the string int resl = 0; // iterating until both pointers meet while (startPtr < endPtr) { // if the characters at the start and end points are equal if (stng.charAt(startPtr) == stng.charAt(endPtr)) { startPtr++; endPtr--; } // else reset start and end pointers else { resl++; startPtr = 0; endPtr = n - resl - 1; } } return resl; } // main method public static void main(String[] args) { MinCharForStringToPalindrome msp = new MinCharForStringToPalindrome(); // provide input string value String strg = "BIBEGDF"; System.out.println("The minimum number of characters required to make palindrome are: "); System.out.println(msp.minCharReqToAdd(strg)); } }
Output:
The minimum number of characters required to make palindrome are: 4
Complexity analysis: The program iterates through string characters, checking if the entire string is a palindrome. The while loop executes n times, and resetting pointers inside the while loop may cause startPtr to revisit characters, which leads to O(n) iterations. Therefore, the overall time complexity is O(n^2), where n is length of the input string. The space complexity is O(1) because constant space for fixed number of variables, irrespective of the input size.
Approach: Using LPS Array of KMP algorithm
We can do better with the help of the KMP algorithm. Observe the steps to solve the problem with the help of the LPS Array of the KMP algorithm.
Step 1: Create an array for storing the LPS values.
Step 2: Use a StringBuilder to effectively modify the input string.
Step 3: Reverse the input string and append it to itself with the special character $ in the middle.
Step 4: Calculate the LPS array for the updated string.
Step 5: Finally, return the minimum number of characters needed by subtracting the length of the original string from the last element of the LPS array.
FileName: MinCharForStringToPalindrome.java
// importing util packages import java.util.*; public class MinCharForStringToPalindrome { // method to calculate array of Longest Prefix, which is also a Suffix (LPS) for a given string public static int[] CalculateArrayOfLPS(String strg) { int nLen = strg.length(); int longPrefSuf[] = new int[nLen]; // array to store LPS values int i = 1, len = 0; longPrefSuf[0] = 0; // initial value of LPS at index 0 is always 0 // iterating through the string to calculate LPS values while (i < nLen) { // if characters at current positions equal if (strg.charAt(i) == strg.charAt(len)) { len++; longPrefSuf[i] = len; i++; } else // if not equal { if (len != 0) { len = longPrefSuf[len - 1]; // update the length to the length of the longest common prefix and suffix } else { longPrefSuf[i] = 0; i++; // move to the next character } } } return longPrefSuf; } // method to get minimum character to be added at beginning to make string palindrome static int minCharReqToAdd(String strg) { // creating StringBuilder to modify the input string StringBuilder sb = new StringBuilder(); sb.append(strg); String revs = sb.reverse().toString();// reversing the String sb.reverse().append("$").append(revs); // append a special character '$' and the reversed string int longPrefSuf[] = CalculateArrayOfLPS(sb.toString()); return strg.length() - longPrefSuf[sb.length() - 1]; } // main method public static void main(String[] args) { MinCharForStringToPalindrome msp = new MinCharForStringToPalindrome(); // provide input string value String strg = "BIBEGDF"; System.out.println("The minimum number of characters required to make palindrome are: "); System.out.println(msp.minCharReqToAdd(strg)); } }
Output:
The minimum number of characters required to make palindrome are: 4
Time Complexity: The CalculateArrayOfLPS method and minCharReqToAdd methods have a linear time complexity of O(n), where n is the input string length. They iterate through the characters of the input string once. Therefore, the overall time complexity is O(n), where n is the length of the input string.
Space complexity: The space complexity is O(n) because the StringBuilder and extra space are required for the reversed string and LPS array. Therefore, the overall space complexity is O(n), where n is the length of the input string.
Approach: Using Z Array of Z Algorithm
The following steps describe an efficient way of solving the problem using the Z array of the Algorithm.
Step 1: Reverse the given string and concatenate it with the original string, separated by a special character, such as '$'.
Step 2: Using the steps below, compute the Z-array for the concatenated string.
Step 2.1: Create a list to store the Z-values, with all initial values set to 0.
Step 2.2: Initialise two pointers, named left and right, for recording the current boundaries of the Z-box.
Step 2.3: Iterate through the string, update Z-values based on previously calculated values, and expand Z-values when characters match.
Step 2.4: update the left and right pointers accordingly.
Step 3: Get the maximum Z-value, which represents the length of the longest common prefix and suffix.
Step 4: Determine the difference between the original length of string and the maximum Z-value to obtain the minimum number of characters required to make it palindrome.
FileName: MinCharForStringToPalindrome.java
// importing util packages import java.util.*; public class MinCharForStringToPalindrome { // method for calculating the Z-array for the specified string. public static ListcalculateArrayOfZ(String strg) { // initialize Z array list with zeros List ZArrList = new ArrayList<>( Collections.nCopies(strg.length(), 0)); // initializing both the left and right pointers int left = 0, right = 0; for (int i = 1; i < strg.length(); i++) { if (i <= right) { // calculating Z value ZArrList.set(i, Math.min(ZArrList.get(i - left), right - i + 1)); } // if characters match, expand Z value while (i + ZArrList.get(i) < strg.length() && strg.charAt(ZArrList.get(i)) == strg.charAt(i + ZArrList.get(i))) { ZArrList.set(i, ZArrList.get(i) + 1); } // if the Z value exceeds the right border, update both the left and right pointers. if (i + ZArrList.get(i) - 1 > right) { left = i; right = i + ZArrList.get(i) - 1; } } return ZArrList; } // method for determining the minimum number of characters to be inserted to make the string into a palindrome. public static int minCharReqToAdd(String strg) { int nLen = strg.length(); // reversing the input string String revStrg = new StringBuilder(strg).reverse().toString(); // combining the original and reversed strings with a special character in between. String concatStrg = strg + "$" + revStrg; int remvChars = Integer.MIN_VALUE; // Computing Z array for the concatenated string List ZArr = calculateArrayOfZ(concatStrg); for (int i = 0; i < ZArr.size(); i++) { if (ZArr.get(i) == concatStrg.length() - i) { remvChars = Math.max(remvChars, ZArr.get(i)); } } return nLen - remvChars; } // main method public static void main(String[] args) { MinCharForStringToPalindrome msp = new MinCharForStringToPalindrome(); // provide input string value String strg = "BIBEGDF"; System.out.println("The minimum number of characters required to make palindrome are: "); System.out.println(msp.minCharReqToAdd(strg)); } }
Output:
The minimum number of characters required to make palindrome are: 4
Complexity Analysis: The time complexity is O(n), because the Z algorithm traverses the input string once and reverses the string and concatenate it. Therefore, the overall time complexity is O(n) where, n is the length of the input String. The overall space complexity is O(n), because the Z-array and concatenated string require O(n) additional space for storage and computation, respectively.