Minimum number of Appends needed to make a string palindrome
Given a string s we need to tell minimum characters to be appended (insertion at the end) to make a string palindrome.
Examples:
Input : s = "abede" Output : 2 We can make string palindrome as "abedeba" by adding ba at the end of the string. Input : s = "aabb" Output : 2 We can make string palindrome as"aabbaa" by adding aa at the end of the string.
The solution can be achieved by removing characters from the beginning of the string one by one and checking if the string is palindrome or not.
For Example, consider the above string, s = “abede”.
We check if the string is palindrome or not.
The result is false, then we remove the character from the beginning of a string and now string becomes “bede”.
We check if the string is palindrome or not. The result is again false, then we remove the character from the beginning of a string and now the string becomes “ede”.
We check if the string is palindrome or not. The result is true, so the output becomes 2 which is the number of characters removed from the string.
Implementation:
C++
// C++ program to find minimum number of appends // needed to make a string Palindrome #include <cstring> #include <iostream> using namespace std; // Checking if the string is palindrome or not bool isPalindrome(string str) { int len = str.length(); // single character is always palindrome if (len == 1) return true ; // pointing to first character string::iterator ptr1 = str.begin(); // pointing to last character string::iterator ptr2 = str.end() - 1; while (ptr2 > ptr1) { if (*ptr1 != *ptr2) return false ; ptr1++; ptr2--; } return true ; } // Recursive function to count number of appends int noOfAppends(string s) { if (isPalindrome(s)) return 0; // Removing first character of string by // incrementing base address pointer. s.erase(s.begin()); return 1 + noOfAppends(s); } // Driver program to test above functions int main() { string s = "abede" ; cout << noOfAppends(s) << endl; return 0; } // This code is contributed by Prajwal Kandekar |
C
// C program to find minimum number of appends // needed to make a string Palindrome #include<stdio.h> #include<string.h> #include<stdbool.h> // Checking if the string is palindrome or not bool isPalindrome( char *str) { int len = strlen (str); // single character is always palindrome if (len == 1) return true ; // pointing to first character char *ptr1 = str; // pointing to last character char *ptr2 = str+len-1; while (ptr2 > ptr1) { if (*ptr1 != *ptr2) return false ; ptr1++; ptr2--; } return true ; } // Recursive function to count number of appends int noOfAppends( char s[]) { if (isPalindrome(s)) return 0; // Removing first character of string by // incrementing base address pointer. s++; return 1 + noOfAppends(s); } // Driver program to test above functions int main() { char s[] = "abede" ; printf ( "%d\n" , noOfAppends(s)); return 0; } |
Java
// Java program to find minimum number of appends // needed to make a string Palindrome class GFG { // Checking if the string is palindrome or not static boolean isPalindrome( char []str) { int len = str.length; // single character is always palindrome if (len == 1 ) return true ; // pointing to first character int ptr1 = 0 ; // pointing to last character int ptr2 = len- 1 ; while (ptr2 >= ptr1) { if (str[ptr1] != str[ptr2]) return false ; ptr1++; ptr2--; } return true ; } // Recursive function to count number of appends static int noOfAppends(String s) { if (isPalindrome(s.toCharArray())) return 0 ; // Removing first character of string by // incrementing base address pointer. s=s.substring( 1 ); return 1 + noOfAppends(s); } // Driver code public static void main(String arr[]) { String s = "abede" ; System.out.printf( "%d\n" , noOfAppends(s)); } } // This code contributed by Rajput-Ji |
Python3
# Python3 program to find minimum number of appends # needed to make a String Palindrome # Checking if the String is palindrome or not def isPalindrome( Str ): Len = len ( Str ) # single character is always palindrome if ( Len = = 1 ): return True # pointing to first character ptr1 = 0 # pointing to last character ptr2 = Len - 1 while (ptr2 > ptr1): if ( Str [ptr1] ! = Str [ptr2]): return False ptr1 + = 1 ptr2 - = 1 return True # Recursive function to count number of appends def noOfAppends(s): if (isPalindrome(s)): return 0 # Removing first character of String by # incrementing base address pointer. del s[ 0 ] return 1 + noOfAppends(s) # Driver Code se = "abede" s = [i for i in se] print (noOfAppends(s)) # This code is contributed by Mohit Kumar |
C#
// C# program to find minimum number of appends // needed to make a string Palindrome using System; class GFG { // Checking if the string is palindrome or not static Boolean isPalindrome( char []str) { int len = str.Length; // single character is always palindrome if (len == 1) return true ; // pointing to first character char ptr1 = str[0]; // pointing to last character char ptr2 = str[len-1]; while (ptr2 > ptr1) { if (ptr1 != ptr2) return false ; ptr1++; ptr2--; } return true ; } // Recursive function to count number of appends static int noOfAppends(String s) { if (isPalindrome(s.ToCharArray())) return 0; // Removing first character of string by // incrementing base address pointer. s=s.Substring(1); return 1 + noOfAppends(s); } // Driver code public static void Main(String []arr) { String s = "abede" ; Console.Write( "{0}\n" , noOfAppends(s)); } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find minimum number of appends // needed to make a string Palindrome // Checking if the string is palindrome or not function isPalindrome(str) { let len = str.length; // single character is always palindrome if (len == 1) return true ; // pointing to first character let ptr1 = 0; // pointing to last character let ptr2 = len-1; while (ptr2 >= ptr1) { if (str[ptr1] != str[ptr2]) return false ; ptr1++; ptr2--; } return true ; } // Recursive function to count number of appends function noOfAppends(s) { if (isPalindrome(s.split( "" ))) return 0; // Removing first character of string by // incrementing base address pointer. s=s.substring(1); return 1 + noOfAppends(s); } // Driver code let s = "abede" ; document.write(noOfAppends(s)); // This code is contributed by unknown2108 </script> |
2
Time Complexity: O(n2)
Auxiliary Space: O(n)
Efficient Approach:
We also have an algorithm taking the help of the Knuth Morris Pratt Algorithm which is O(n) Time Complexity.
The basic idea behind the approach is that we calculate the largest substring from the end can be calculated and the length of the string minus this value is the minimum number of appends. The logic is intuitive, we need not append the palindrome and only those which do not form the palindrome. To find this largest palindrome from the end, we reverse the string, calculate the DFA and reverse the string again(thus gaining back the original string) and find the final state, which represents the number of matches of the string with the revered string and hence we get the largest substring that is a palindrome from the end, in O(n) time.
Below is the implementation of the above approach:
C++
// CPP program for above approach #include <algorithm> #include <iostream> #include <string> using namespace std; // This class builds the dfa and // precomputes the state. // See KMP algorithm for explanation class kmp_numeric { private : int n; int ** dfa; public : kmp_numeric(string& s) { n = s.length(); int c = 256; // Create dfa dfa = new int *[n]; // Iterate from 0 to n for ( int i = 0; i < n; i++) dfa[i] = new int ; int x = 0; // Iterate from 0 to n for ( int i = 0; i < c; i++) dfa[0][i] = 0; // Initialise dfa[0][s[0]] = 1 dfa[0][s[0]] = 1; // Iterate i from 1 to n-1 for ( int i = 1; i < n; i++) { // Iterate j from 0 to c - 1 for ( int j = 0; j < c; j++) { dfa[i][j] = dfa[x][j]; } dfa[i][s[i]] = i + 1; x = dfa[x][s[i]]; } } // This function finds the overlap // between two strings,by // changing the state. int longest_overlap(string& query) { // q1 is length of query int ql = query.length(); int state = 0; // Iterate from 0 to q1 - 1 for ( int i = 0; i < ql; i++) { state = dfa[state][query[i]]; } return state; } }; int min_appends(string& s) { // Reverse the string. reverse(s.begin(), s.end()); // Build the DFA for the // reversed String kmp_numeric kmp = s; // Get the original string back reverse(s.begin(), s.end()); // Largest overlap in this case is the // largest string from the end which // is a palindrome. int ans = s.length() - kmp.longest_overlap(s); return ans; } // Driver Code int main() { string s = "deep" ; // Answer : 3 string t = "sososososos" ; // Answer : 0 cout << min_appends(s) << endl; cout << min_appends(t) << endl; } |
Java
// Java program for above approach import java.io.*; import java.util.*; // This class builds the dfa and precomputes the state. See // KMP algorithm for explanation class KMPNumeric { private int n; private int [][] dfa; KMPNumeric(String s) { n = s.length(); int c = 256 ; // Create dfa dfa = new int [n]; int x = 0 ; // Iterate from 0 to c - 1 for ( int i = 0 ; i < c; i++) dfa[ 0 ][i] = 0 ; // Initialise dfa[0][s[0]] = 1 dfa[ 0 ][s.charAt( 0 )] = 1 ; // Iterate i from 1 to n-1 for ( int i = 1 ; i < n; i++) { // Iterate j from 0 to c - 1 for ( int j = 0 ; j < c; j++) { dfa[i][j] = dfa[x][j]; } dfa[i][s.charAt(i)] = i + 1 ; x = dfa[x][s.charAt(i)]; } } // This function finds the overlap between two strings, // by changing the state. public int longestOverlap(String query) { // q1 is length of query int ql = query.length(); int state = 0 ; // Iterate from 0 to q1 - 1 for ( int i = 0 ; i < ql; i++) { state = dfa[state][query.charAt(i)]; } return state; } } class GFG { static int minAppends(String s) { // Reverse the string String reversed = new StringBuilder(s).reverse().toString(); KMPNumeric kmp = new KMPNumeric(reversed); // Build the DFA for the reversed string int overlap = kmp.longestOverlap(s); // Largest overlap in this case is the largest // string from the end which is a palindrome. int ans = s.length() - overlap; return ans; } public static void main(String[] args) { String s = "deep" ; // Answer : 3 String t = "sososososos" ; // Answer : 0 System.out.println(minAppends(s)); System.out.println(minAppends(t)); } } // This code is contributed by sankar. |
Python3
class kmp_numeric: def __init__( self , s: str ): n = len (s) c = 256 # Create dfa self .dfa = [[ 0 for _ in range (c)] for _ in range (n)] x = 0 # Initialise dfa[0][s[0]] = 1 self .dfa[ 0 ][ ord (s[ 0 ])] = 1 # Iterate i from 1 to n-1 for i in range ( 1 , n): # Iterate j from 0 to c - 1 for j in range (c): self .dfa[i][j] = self .dfa[x][j] self .dfa[i][ ord (s[i])] = i + 1 x = self .dfa[x][ ord (s[i])] def longest_overlap( self , query: str ) - > int : # q1 is length of query ql = len (query) state = 0 # Iterate from 0 to q1 - 1 for i in range (ql): state = self .dfa[state][ ord (query[i])] return state def min_appends(s: str ) - > int : # Reverse the string. s_reversed = s[:: - 1 ] # Build the DFA for the reversed String kmp = kmp_numeric(s_reversed) # Get the original string back s_reversed = s_reversed[:: - 1 ] # Largest overlap in this case is the # largest string from the end which # is a palindrome. ans = len (s) - kmp.longest_overlap(s_reversed) return ans # Driver Code if __name__ = = '__main__' : s = "deep" # Answer : 3 t = "sososososos" # Answer : 0 print (min_appends(s)) print (min_appends(t)) |
Javascript
// Javascript program for the above approach class kmp_numeric { constructor(s) { let n = s.length; let c = 256; // Create dfa this .dfa = Array.from(Array(n), () => new Array(c).fill(0)); let x = 0; // Initialise dfa[0][s[0]] = 1 this .dfa[0][s.charCodeAt(0)] = 1; // Iterate i from 1 to n-1 for (let i = 1; i < n; i++) { // Iterate j from 0 to c - 1 for (let j = 0; j < c; j++) { this .dfa[i][j] = this .dfa[x][j]; } this .dfa[i][s.charCodeAt(i)] = i + 1; x = this .dfa[x][s.charCodeAt(i)]; } } longest_overlap(query) { // q1 is length of query let ql = query.length; let state = 0; // Iterate from 0 to q1 - 1 for (let i = 0; i < ql; i++) { state = this .dfa[state][query.charCodeAt(i)]; } return state; } } function min_appends(s) { // Reverse the string. let s_reversed = s.split( '' ).reverse().join( '' ); // Build the DFA for the reversed String let kmp = new kmp_numeric(s_reversed); // Get the original string back s_reversed = s_reversed.split( '' ).reverse().join( '' ); // Largest overlap in this case is the // largest string from the end which // is a palindrome. let ans = s.length - kmp.longest_overlap(s_reversed); return ans; } // Driver Code let s = "deep" ; // Answer : 3 let t = "sososososos" ; // Answer : 0 console.log(min_appends(s)); console.log(min_appends(t)); // This code is contributed by adityashatmfh |
C#
using System; class KMPNumeric { private int n; private int [][] dfa; public KMPNumeric( string s) { n = s.Length; int c = 256; // Create dfa dfa = new int [n][]; // Iterate from 0 to n for ( int i = 0; i < n; i++) dfa[i] = new int ; int x = 0; // Iterate from 0 to n for ( int i = 0; i < c; i++) dfa[0][i] = 0; // Initialise dfa[0][s[0]] = 1 dfa[0][s[0]] = 1; // Iterate i from 1 to n-1 for ( int i = 1; i < n; i++) { // Iterate j from 0 to c - 1 for ( int j = 0; j < c; j++) { dfa[i][j] = dfa[x][j]; } dfa[i][s[i]] = i + 1; x = dfa[x][s[i]]; } } // This function finds the overlap // between two strings,by // changing the state. public int LongestOverlap( string query) { // q1 is length of query int ql = query.Length; int state = 0; // Iterate from 0 to q1 - 1 for ( int i = 0; i < ql; i++) { state = dfa[state][query[i]]; } return state; } } class MinimumAppends { public static int MinAppends( string s) { // Reverse the string. char [] charArray = s.ToCharArray(); Array.Reverse(charArray); s = new string (charArray); // Build the DFA for the reversed String KMPNumeric kmp = new KMPNumeric(s); // Get the original string back charArray = s.ToCharArray(); Array.Reverse(charArray); s = new string (charArray); // Largest overlap in this case is the // largest string from the end which // is a palindrome. int ans = s.Length - kmp.LongestOverlap(s); return ans; } static void Main( string [] args) { string s = "deep" ; // Answer : 3 string t = "sososososos" ; // Answer : 0 Console.WriteLine(MinAppends(s)); Console.WriteLine(MinAppends(t)); } } |
3 0
Suggestion by: Pratik Priyadarsan
Time Complexity: O(n2)
Auxiliary Space: O(n2)
Related Article :
Dynamic Programming | Set 28 (Minimum insertions to form a palindrome)