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 end) to make a string palindrome.

Examples:

`Input : s = "abede"Output : 2We can make string palindrome as "abedeba"by adding ba at the end of the string.Input : s = "aabb"Output : 2We 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 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 string and now 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 of above approach:

// 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
s++;
return 1 + noOfAppends(s);
}
// Driver program to test above functions
int main()
{
char s[] = "abede";
printf("%d\n", noOfAppends(s));
return 0;
}

Output

`2`

The above approach described and O(n**2) approach.

Efficient Approach:

We also have an algorithm taking the help of 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 finding 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:

// 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++) {
// Itearte 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";
string t = "sososososos";
cout << min_appends(s) << endl;
cout << min_appends(t) << endl;
}

Output
`30`

More Articles of M Mounika:

Name Views Likes
C++ Segmented Sieve (Print Primes In a Range) 163 0
C++ Sieve Of Erastosthenes 136 0
C++ Gold Mine Problem 295 0
C++ Merge K Sorted Arrays 117 0
C++ K Centers Problem 240 0
C++ Find Nth Catalan Number 311 0
C++ Inplace Rotate square matrix by 90 degrees 286 0
C++ Find Non Repeating Elements in Array 87 0
C++ Merge Two Binary Trees 121 0
C++ Sum of Numbers From Root To Leaf Paths 89 0
C++ Meta Strings 92 0
C++ Flood Fill Algorithm 402 0
C++ smallest substring with maximum distinct characters 200 0
C++ Smallest window with all characters in string 94 0
C++ Minimum Removal of Characters from string to make its permutation as palindrome 87 0
C++ Minimum characters added at front of string in palindrome conversion 70 0
C++ Number of Bracket Reversals needed to make expression Balanced 73 0
C++ String to Palindrome with Append Function 84 0
C++ WildCard pattern matching 76 0
C++ Anagram substring Search 72 0
C++ Manachars Algorithm 74 0
C++ Search String in Grid 84 0
C++ String Matching(Z Algorithm) 67 0
C++ String Matching(Naive Algorithm) 115 0
C++ String Matching(KMP Algorithm) 141 0
C++ Remove Duplicates From String 111 0
C++ Basics of String Manipulation 85 1
C++ Disjoint Data Structure Cycle Detection 87 0
C++ Problem On Disjoint Data Structures 95 0
C++ Disjoint Data Structures Part3 79 0
Disjoint Data Structures Part2 91 0
Disjoint Data Structures 93 1
C++ Segment Trees 321 2
C++ Trie Cost of Data 291 1
C++ Trie Datastructure 279 1
C++ Greedy Approach Minimum number of coins 526 0
C++ Greedy Approach Maximum height Pyramid 329 1
C++ Greedy Approach String lexicographically largest subsequence 247 0
C++ Greedy Approach Lexicographically largest subsequence 364 0
C++ Greedy Approach Prims MST 398 1
C++ Greedy Approach Krushkals MST 458 1
C++ Greedy Approach N-array maximum sum 334 1
C++ Greedy Approach Policemen Catch Thieves 563 1
C++ Greedy Approach Maximum product Subset 546 1
C++ Greedy Approach Minimum Product Subset 349 1
C++ Greedy Approach Fractional Knapsack 737 1
C++ Greedy Approach-Activity Selection Problem 745 1
C++ Greedy Approach-Egyptian Fractions 640 0
C++ Greedy Approach-Huffman Codes 1031 1
C++ Introduction to Greedy Approach 955 2