Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Here is psedocode mixed with code as solution.
Create new string that holds the reverse of given string and append the input string to it..
char [] newString = new char[s.length + (s.length - 1)]
char [] currentString = 'You'
for (int i=0; i< currentString.length; i++)
{
newstring[i] = currentString [currentString.length -i]
}
for (int i=currentString.length+1; i< newString.length ; i++)
{
newstring[i] = currentString [i]
}
Console.WriteLine((string) newstring) ;
Well, I believe the solution is very simple. You just need to compare suffixes of reverse string with prefixes of input string and find the longest in common. there is no need to construct a prefix/suffix tree (You can, but I didn't for sake of simplicity). Here is the code in Java, with O(n). Note that you can combine the last three loops in one, and avoid using additional space I used for tmp1[] and tmp2[].
public static int getMinCharToPalindrom2(String input){
//Create the reverse of input string
StringBuffer sb = new StringBuffer();
for(int i=input.length()-1; i> -1; i--)
sb.append(input.charAt(i));
String reverse = sb.toString();
String[] tmp1= new String[reverse.length()];
String[] tmp2 = new String[input.length()];
//Populate an array with suffixes of reverse string, such that array[0] contains the shortest suffix
for(int i=reverse.length()-1; i>-1; i--)
tmp1[reverse.length()-i-1] = reverse.substring(i,reverse.length());
//Populate an array with prefixes of input string, such that array[0] contains the shortest prefix
for(int i=0; i<input.length(); i++)
tmp2[i] = input.substring(0,i+1);
//Start from the end of arrays, and find the biggest sub-string in common
for(int i=input.length()-1; i>-1; i--){
if(tmp1[i].equals(tmp2[i])){
return (2*input.length())-tmp1[i].length();
}
}
return -1;
}
All you need it is to found the biggest such palindrone that s = prefix + palindrom.
You can do it in O(N^2), but it is better to use Manacher algorithm for finding all subpalindromes in O(N) and add reversed prefix to the and.
s = prefix + palindrome + reverse(prefix)
You only need subpalindrom that start from the beginning of the string. It should simplify any subpolindrome finding technique.
public int getShortestFrontModdedPalen(String str){
if(str == null){
throw new NullPointerException():
}
int definatelyAdd = 0;
int nonChanges = 0;
int endPos = str.length() -1;
int frontPos = 0;
while(endPos > frontPos){
if(str.charAt(endPos) == str.charAt(frontPos)){
nonChanges += 1;
endPos--;
frontPos++;
}
else{
frontPos = 0;
definatelyAdd+= 1 + nonChanges;
nonChanges = 0;
endPos--;
}
}
return definatelyAdd + str.length();
}
package google;
/**
*
* @author nly22805
*
* Given a string S, you are allowed to convert it to a palindrome by adding 0 or more characters in front of it.
* Find the length of the shortest palindrome that you can create from S by applying the above transformation.
*/
public class Palindromes {
private String str;
public Palindromes(String s) {
str = s;
}
private boolean isPalindrome(String s) {
int start = (int)(s.length() / 2) - 1;
for (int i = start, j = start + ((s.length() % 2 == 0) ? 1 : 2); (i >= 0) && (j < s.length()); i--, j++) {
if (s.charAt(i) != s.charAt(j)) return false;
}
return true;
}
public String makePalindrome() {
int index = 0;
String subPalindrome = "";
for (int i = 2; i <= str.length(); i++) {
String subString = str.substring(0, i);
if (isPalindrome(subString)) {
index = i;
subPalindrome = subString;
break;
}
}
StringBuffer palindrome = new StringBuffer(str);
if (index < str.length()) {
for (int i = index; i < str.length(); i++) {
palindrome.insert(0, str.charAt(i));
}
}
return palindrome.toString();
}
public static void main(String[] args) {
Palindromes p = new Palindromes("racexyzart");
System.out.println(p.makePalindrome());
}
}
#include<iostream>
#include <list>
using namespace std;
void makePalindrome(char arr[],int len)
{
int front=0, end=len-1;
char result[100];
int i=0;
while(front != end)
{
if( arr[front] == arr[end])
{
result[i]=arr[front];
front++;
end--;
i++;
}
else
{
result[i]=arr[end];
i++;
end--;
}
}
result[i]='\0';
//printing the result for test
i=0;
while(result[i] != '\0')
cout<<result[i++];
i=0;
while(arr[i] != '\0')
cout<<arr[i++];
}
int main()
{
char a[]="racexyzart";
makePalindrome(a,10);
return 1;
}
I look for the shortest Palindrome where the first char is the first char of String s. Then I find the length of the part of the string that isn't a palindrome and add it to the length of string s. This should be O(n) because the end pointer never resets
public int shortestPalindromePossible(String s)
{
if(s.length() == 0) return 0;
int start = 0;
int end = s.length() - 1;
int realend = s.length() - 1;
while(start < end) {
if(s.charAt(start) == s.charAt(end))
{
start++;
end--;
continue;
}
if(start == 0) {
end--;
}
start = 0;
realend = end;
}
return (s.length() - (realend + 1)) + s.length();
}
This isn't O(n). It is O(n^2). Consider this input: 10 1's a 2 then a 9 1s.
11111111112111111111
The algorithm first does 10 comparisons to check with pivot like below
1111111111 | 2111111111
Then 8 comparisons for this:
111111111 | 1211111111 1
Then 7 comparisons for this:
11111111 | 1121111111 11
And so on.
Generally
(n/2 + 1) * n/4
So O(n^2)
I'm confused about your explanation. I don't think that is what my algorithm is doing.
Let's use this example which is similar to yours: 3 1's a 2 then 2 1s.
111211
First you have a pointer at the first and last chars. This will be represented by brackets
[1]1121[1]
You compare these two chars. If they are the same, increment the first pointer and decrement the last pointer.
1[1]12[1]1
Compare again. Both are equal
11[1][2]11
These two chars are different. Now you set the start pointer back to the beginning and compare
[1]11[2]11
They aren't equal again, but with my logic you only decrement the last pointer
[1]1[1]211
These are the same pointers
1[[1]]1211
Now we know 111 is the smallest palindrome where the first char is the first char of the original string. Now we find the length of the string that isn't part of the palindrome and add it to the original length which will be your answer. This example answer is 9. (112111211)
Try 112111. The longest palindrome should be 11211 with length 5. The output of this algorithm is incorrect.
This can be done in O(n) time and O(n+e) space for the newly constructed string.
The input string might have palindrome as prefix or not.
palindrome prefix checking is simple and O(n).
If the input string does not have any palindrome as any part of prefix, we reverse the 1 to n-1 index string and append it at the front.
If there is any palindrome of size 2 or more as prefix, then the remaining string is reversed and appended at the front. that e is the part of the non-palindrome prefix. At the most, it can be n-1.
public class ShortestPalindrome {
public int getShortestPalindromeLength(String str){
if(str == null){
throw new NullPointerException();
}
int count = 0;
int endPos = str.length() -1;
int frontPos = 0;
StringBuilder sb = new StringBuilder();
sb.append(str);
while(!isPalindrome(sb.toString()) && frontPos < endPos){
sb.insert(0,str.charAt(++frontPos));
count++;
}
return count+ str.length();
}
private boolean isPalindrome(String str) {
int endPos = str.length() -1;
int frontPos = 0;
while(endPos > frontPos){
if(str.charAt(frontPos++) != str.charAt(endPos--)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
ShortestPalindrome obj = new ShortestPalindrome();
System.out.println(obj.getShortestPalindromeLength("racexyzart"));
}
}
I think for "abaa" the length should be 3, as we only need to append three more characters to the front to make this a palindrome.
"abaa" => "aab" + "abaa" which when combined is a palindrome.
public class ShortestPalindrome {
public int getShortestPalindromeLength(String str){
if(str == null){
throw new NullPointerException();
}
int count = 0;
int endPos = str.length() -1;
int frontPos = 0;
StringBuilder sb = new StringBuilder();
sb.append(str);
while(!isPalindrome(sb.toString()) && frontPos < endPos){
sb.insert(0,str.charAt(++frontPos));
count++;
}
return count+ str.length();
}
private boolean isPalindrome(String str) {
int endPos = str.length() -1;
int frontPos = 0;
while(endPos > frontPos){
if(str.charAt(frontPos++) != str.charAt(endPos--)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
ShortestPalindrome obj = new ShortestPalindrome();
System.out.println(obj.getShortestPalindromeLength("racexyzart"));
}
}
public static String makePalindrom(String s)
{
StringBuilder sb = new StringBuilder();
for (int i = s.length() - 1; i > 0; i--) {
// check if s[0..i] is a palindrom
int j;
for (j = 0; j < (i+1)/2; j++)
if (s.charAt(j) != s.charAt(i-j))
break;
if (j == (i+1)/2)
break; // [0..i] is a palindrom
sb.append(s.charAt(i));
}
sb.append(s);
return sb.toString();
}
Best solution here is to use a Knuth-Morris-Pratt algorithm. It runs in O(n) time, requires 2*n additional space and extremely fast and easy to code. The main idea is - we construct new string that contains our string + some symbol that can't be in our string, for instance '$' + reversed our string. After that we need to run KMP for that string to calculate prefix function. The answer is the length of our starting string minus prefix function value of the last element of the new string.
prefix function for every position i in the string shows the maximum length of prefix for the string s [0...i] that equals to suffix of the string s[0...i].
So if we construct new string in the way described above, prefix function for the last element will show the maximum size of the palindrome in the beginning of our string. All we have to do is to add in front of our string the rest of the characters.
int getPalindrome(string s) {
int p[2000011], n = s.size();
string current = s + '$';
for (int i = 0; i < n; i++) {
current += s[n - 1 - i];
}
p[0] = 0;
for (int i = 1; i < 2 * n + 1; i++) {
int j = p[i - 1];
while (j > 0 && current[j] != current[i])
j = p[j - 1];
j += current[i] == current[j];
p[i] = j;
}
return n - p[2 * n];
}
In this code I returned the number of characters you need to add. To get the final length of the palindrome:
return 2*n - p[2 * n];
looks like a dynamic programming question. you have few options:
The minimum number of insertions in the string str[l…..h] can be given as:
minInsertions(str[l+1…..h-1]) if str[l] is equal to str[h]
min(minInsertions(str[l…..h-1]), minInsertions(str[l+1…..h])) + 1 otherwise
here is a ruby answer:
def min_insert str, left=0, right=nil
right ||= str.size-1
return Float::INFINITY if left > right
return 0 if left == right
return 0 if left == right-1
if str[left] == str[right] then min_insert(str, left+1, right-1) else [min_insert(str,left+1, right), min_insert(str,left,right-1)].min + 1 end
end
p min_insert 'geeks'
#return 3
This is a DP solution. O(n^2) time.
Given a string x1, x2, x3, ...,xn you can do the following:
Either add character at beginning, which will be xn
or pass if x1 == xn.
dp[1, n] = min (dp[2, n - 1] + COST_PASS, dp[1, n - 1] + COST_INSERT).
COST_INSERT = 1;
COST_PASS = 0 if the first and last characters of substring are equal, or INF.
Here is the code (it only returns the number of insertions. the total length will be length of string + number of insertions.).
public class MakePlindromic {
private int[][] dp;
private String x;
public int Solve(String x) {
this.x = x;
dp = new int[x.length()][x.length()];
for (int[] arr : dp) Arrays.fill(arr, -1);
return makePalindromic(0, x.length() - 1);
}
private int makePalindromic(int i, int j) {
if (j <= 1) return 0;
if (dp[i][j] == -1) {
char first = x.charAt(i), last = x.charAt(j);
int costInsert = 1, costPass = 1000000;
if (first == last) {
costPass = 0;
}
int pass = makePalindromic(i + 1, j - 1) + costPass;
int ins = makePalindromic(i, j - 1) + costInsert;
dp[i][j] = Math.min(pass, ins);
}
return dp[i][j];
}
public static void main(String[] args) {
String test1 = "racexyzart";
String test2 = "abddcdd";
String test3 = "aacecaaa";
MakePlindromic solve = new MakePlindromic();
System.out.println(solve.Solve(test1));
System.out.println(solve.Solve(test2));
System.out.println(solve.Solve(test3));
}
}
/// Returns: 5, 5, 1
This is not as complex as you think. It is not the problem of adding characters to make a string a palindrome. It is much simpler. It is just adding characters only to the beginning of the string. Insertions are only in the beginning,
You just need to compare the last character to the first character. If these two are the same then you check if the rest of the string is a palindrome. If it is then no additions required.
Otherwise you add one to the count and check for the last but one character and so on.
Here is a recursive solution:
#include<stdio.h>
#include<string.h>
int is_pallin(char X[], int l, int h)
{
while(l<h)
{
if(X[l] != X[h])
return 0;
++l;
--h;
}
return 1;
}
int no_pallin(char X[], int l, int h)
{
if(l == h)
return 0;
if(X[l] == X[h])
if(is_pallin(X, l+1, h-1))
return 0;
int t = (1 + no_pallin(X, l, h-1));
return t;
}
int main()
{
int n;
char X[] = "aaacecaaa";
n = strlen(X);
printf("The result number of %s is : %d\n",X,no_pallin(X,0,n-1) + n);
char Y[] = "acecaaa";
n = strlen(Y);
printf("The result number of %s is : %d\n",Y,no_pallin(Y,0,n-1) + n);
char Z[] = "racexyzart";
n = strlen(Z);
printf("The result number of %s is : %d\n",Z,no_pallin(Z,0,n-1) + n);
}
This is an O(n) solution.
The output is:
The result number of aaacecaaa is : 9
The result number of acecaaa is : 9
The result number of racexyzart is : 19
Your solution fails for racexyzart, where the resultant string is trazyxcecxyzart whose length is 15.
how do you get trazyxcecxyzart ? The problem says to add characters in FRONT of the string, not anywhere in the string.
So, racexyzart would be trazyxecaracexyzart = 19.
Start xorring the chats from left to right and note the longest string where it is 0. Then take the remainder of the string, reverse it and add it to the beginning.
public class PalindromeFinder {
public String findPalindrome(String s){
if(s.isEmpty()) return s;
int mid = s.length()/2;
String left, right;
while(mid>0){
left = getReverse(s.substring(0, mid));
right = s.substring(mid+1,s.length());
if(right.length()>=left.length() && left.equals(right.substring(0,left.length()))){ //If the result is an odd length palindrome
String append = right.substring(left.length(), right.length());
return getReverse(append)+ s;
} else if(s.charAt(mid-1)==s.charAt(mid)){ //if the result is an even length palindrome
left = getReverse(s.substring(0, mid-1));
if(left.equals(right.substring(0,left.length()))) {
String append = right.substring(left.length(), right.length());
return getReverse(append)+ s;
}
}
mid--;
}
return getReverse(s.substring(1,s.length()))+s;
}
public String getReverse(String s){
return new StringBuilder(s).reverse().toString();
}
}
bool isPalindrome(char* s, int n, int* i)
{
if (n < 2)
return true;
int start = 0;
int end = n - 1;
while (start < end)
{
if (s[start] != s[end])
{
*i = start;
return false;
}
start++;
end--;
}
return true;
}
int sizeofPalindrome(char* s, int n)
{
if (n < 2)
return 0;
int faultyIndex = 0;
if (isPalindrome(s, n, &faultyIndex))
return 0;
else
return n - faultyIndex;
}
I might be thinking this wrong, but here's what I think..
If you have a palindrome string already. There's nothing there to do. If not, we find the first index of the non palindromic string, and we will have to append the rest of the string, as any other appends won't guarantee a palindromic string.
Please give me some edge cases to break my solution. It will help me improve and understand my fault (if any)
The above time is O(n) and just one traversal, without additional space. It just returns the length of the string that has to be prepended
The solution can be constructed thinking of the problem as
length(string, start_index, end_index)
and constructing the final solution from the subproblems.
A python implementation would be:
def finalLength(string):
length = len(string)
def genValue(i, j):
if j < i:
return -1
elif j >= i:
return 0
cache = [[genValue(i, j) for i in xrange(length)] for j in xrange(length)]
def additionCount(string, start, end):
if cache[start][end] < 0:
if string[start] == string[end]:
cache[start][end] = additionCount(string, start+1, end-1)
cache[start][end] = min(
cache[start][end],
1+min(
additionCount(string, start+1, end),
additionCount(string, start, end-1)
)
)
else:
cache[start][end] = 1+min(
additionCount(string, start+1, end),
additionCount(string, start, end-1))
return cache[start][end]
return additionCount(string, 0, length-1)
Here is a modified/simplified version of Maxxx's above. It contains two loops, but with worst case run time at O(n). The inner loop will not run more than n/2 times, so O(n + n/2) = O(n).
Ex. "aaaaaxyaaaaa".
When it gets to 'x' and 'y', it will be halfway through the string, and run n/2 times to find a new starting point.
Here's the code:
int FindPalindromeSize(string s)
{
// n is the number of matching letters
int n = 0;
// r is the reverse string navigator
for (int r = s.length() - 1; r >= 0; --r)
{
while(n > 0 && (s[r] != s[n]))
{
n--; // Keep subtracting n until we match again or reach the beginning again
}
// If we have a match, move to the next letter
if (s[r] == s[n]) { n++; }
}
// original string, plus the difference of non-palindrome-y letters
// s.length() + s.length() - n;
return (s.length()*2) - n;
}
Python implementation
def isPalindrome(s):
if len(s) < 2:
return True
if s[0] != s[-1]:
return False
elif s[0] == s[-1]:
return isPalindrome(s[1:-1])
def longestPal(s):
for i in range(len(s)):
if isPalindrome(s[:len(s) - i]):
return len(s) - i
def reverse(s):
s_rev = ''
for i in range(len(s)):
s_rev += s[len(s) - 1 - i]
return s_rev
def getRest(s):
i = longestPal(s)
rest = s[i:]
return rest
def minPal(s):
rest = getRest(s)
rest = reverse(rest)
s = rest + s
return s, len(rest)
s = 'abccbadsf'
print minPal(s)
Another Python Code:
def palindrome(string):
''' returns if a string is a palindrome or not'''
if len(string)%2==0:
return string[:len(string)/2]==string[len(string)/2:][::-1]
else:
return string[:len(string)/2]==string[(len(string)/2)+1:][::-1]
def makeAPalindrome(string):
if palindrome(string):
print '%s is a palindrome'%string
else:
temp=''
for i in range(len(string)):
newstr=string[:(len(string)-1)-i]
if palindrome(newstr):
temp=newstr
break
temp=string[(string.find(temp)+len(temp)):][::-1]+string
print 'By adding %d char(s), %s becomes a palindrome: %s'%(len(temp)-len(string),string,temp)
Another Python Implementation:
def palindrome(string):
''' returns if a string is a palindrome or not'''
if len(string)%2==0:
return string[:len(string)/2]==string[len(string)/2:][::-1]
else:
return string[:len(string)/2]==string[(len(string)/2)+1:][::-1]
def makeAPalindrome(string):
if palindrome(string):
print '%s is a palindrome'%string
else:
temp=''
for i in range(len(string)):
newstr=string[:(len(string)-1)-i]
if palindrome(newstr):
temp=newstr
break
temp=string[(string.find(temp)+len(temp)):][::-1]+string
print 'By adding %d char(s), %s becomes a palindrome: %s'%(len(temp)-len(string),string,temp)
public class Solution
{
public int makeP(String s,int start,int end)
{
if(end<=start)//if the string has length less than or equal to 1
{
return 0;
}
//If the characters at 'start' and 'end' are the same increase 'start' by 1,
//decrease 'end' by 1, and make a recursive call.
if(s.charAt(start)==s.charAt(end))
{
return(makeP(s,++start,--end));
}
//If a mismatch between char at 'start' and char at 'end' occurrs at the terminal
//ends of the string (0 and s.length()-1).
if(start==0)
{
//Remove the character at s.length()-1
s=s.substring(start,end);
//Add 1 to the total count of characters to be replaced.
///make a recursive call with 'start'=0 and 'end'=s.length()-1
return 1 + makeP(s,0,s.length()-1);
}
//If character mismatch occurrs somewhere in the middle of the string
//(not at terminal ends).
//The number of characters to add is defined as:
// 1 Less than The number of characters before 'start'-- (start-1) +
//The number of characters from 'start' to the end of the string (s.length()-start)
return ((start-1)+(s.length()-start));
}
}
I found solution using palindromic tree data structure
import java.util.*;
import java.io.*;
public class Main{
BufferedReader in;
StringTokenizer str = null;
PrintWriter out;
private String next() throws Exception{
if (str == null || !str.hasMoreElements())
str = new StringTokenizer(in.readLine());
return str.nextToken();
}
private int nextInt() throws Exception{
return Integer.parseInt(next());
}
char []s;
int suff, n;
int size = 0;
Node []tree;
final static int MAX = 100000;
public void run() throws Exception{
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
StringBuilder sb = new StringBuilder();
sb.append(next());
sb.reverse();
s = sb.toString().toCharArray();
n = s.length;
init();
int len = tree[suff].len;
out.println(n - len);
out.close();
}
private boolean addLetter(int pos) {
int cur = suff, curlen = -1;
int to = s[pos] - 'a';
while(true) {
curlen = tree[cur].len;
if (pos - curlen - 1 >= 0 && s[pos - curlen - 1] == s[pos]) {
break;
}
cur = tree[cur].sufflink;
}
if (tree[cur].next[to] != -1) {
suff = tree[cur].next[to];
return false;
}
int v = size++;
suff = v;
tree[v] = new Node(tree[cur].len + 2);
tree[cur].next[to] = v;
if (tree[v].len == 1) {
tree[v].sufflink = 1;
return true;
}
while(true) {
cur = tree[cur].sufflink;
curlen = tree[cur].len;
if (pos - curlen - 1 >= 0 && s[pos - curlen - 1] == s[pos]) {
tree[v].sufflink = tree[cur].next[to];
break;
}
}
return true;
}
private void init() {
tree = new Node[MAX];
tree[size] = new Node(-1);
tree[size].sufflink = size++;
tree[size] = new Node(0);
tree[size++].sufflink = 0;
suff = size - 1;
}
class Node {
int next[];
int sufflink;
int len;
public Node(int len) {
this.len = len;
sufflink = -1;
this.len = len;
next = new int[26];
Arrays.fill(next, -1);
}
public String toString() {
return "[len=" + this.len + ", sufflink=" + this.sufflink + "]";
}
}
public static void main(String args[]) throws Exception{
new Main().run();
}
}
Sorry, wrong body of algorithm. This is one is correct. O(n) - space, O(n) - complexity
public void run() throws Exception{
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
StringBuilder sb = new StringBuilder();
sb.append(next());
sb.reverse();
s = sb.toString().toCharArray();
System.out.println(Arrays.toString(s));
n = s.length;
init();
for(int i = 0; i < n; ++i) addLetter(i);
int len = tree[suff].len;
out.println(n - len);
out.close();
}
using System;
namespace CareerCup
{
public class ShortestPalindrome
{
public int GetShortestPalindromeLength(string input)
{
if (string.IsNullOrEmpty(input))
{
throw new ArgumentNullException("input");
}
int leadingCharsNumber = 0;
while (leadingCharsNumber < input.Length)
{
bool flag = true;
for (int i = 0, j = input.Length - 1 - leadingCharsNumber;
i < j;
i++, j--)
{
if (input[i] != input[j])
{
flag = false;
break;
}
}
if (flag)
{
break;
}
leadingCharsNumber++;
}
return leadingCharsNumber + input.Length;
}
}
}
Start at the mid and check the two string from the mid ( [0---mid] vs [mid+1 ---input.Length]. if while checking starting the mid and we reach at the beginning , that mean we have the longest palindorm and fill the remaining from the second string to the front of the first string. Here is a c# code
string ConverteToPalindrom(string input)
{
int mid = (input.Length / 2);
for (int i = mid; i >= 0; i--)
{
int j = i, k = i + 1;
for (; j >= 0; j--, k++)
{
if (input[j] != input[k])
{
break;
}
}
if (j <= 0)
{
var temp = input;
while (k < temp.Length)
{
input = temp[k++] + input;
}
break;
}
}
return input;
}
Algo:
First check if the string S is already a palindrome - mirror test (Ci==Cn-1-i, i=0 to n/2)
If Yes, the shortest length is S's length. i.e. n
If No, find the minimum addition to make it a palindrome:
Use the ith char as pivot (i = (n/2-1) to 0)
If S' left part is the mirror of S's right part with the ith char as pivot (Cj==Ci+i-j)
the minimum addition is: delta = (n-2*i-1) and thus the shortest length=n+delta=2*n-2*i-1
return the shortest length
Note: if want to ignore space in the string S, pre-process the S to make a new S' w/o space
Algo:
First check if the string S is already a palindrome - mirror test (Ci==Cn-1-i, i=0 to n/2)
If Yes, the shortest length is S's length. i.e. n
If No, find the minimum addition to make it a palindrome:
Use the ith char as pivot (i = (n/2-1) to 0)
If S' left part is the mirror of S's right part with the ith char as pivot (Cj==Ci+i-j)
the minimum addition is: delta = (n-2*i-1) and thus the shortest length=n+delta=2*n-2*i-1
return the shortest length
Note: if want to ignore space in the string S, pre-process the S to make a new S' w/o space
{Algo:
First check if the string S is already a palindrome - mirror test (Ci==Cn-1-i, i=0 to n/2)
If Yes, the shortest length is S's length. i.e. n
If No, find the minimum addition to make it a palindrome:
Use the ith char as pivot (i = (n/2-1) to 0)
If S' left part is the mirror of S's right part with the ith char as pivot (Cj==Ci+i-j)
the minimum addition is: delta = (n-2*i-1) and thus the shortest length=n+delta=2*n-2*i-1
return the shortest length
Note: if want to ignore space in the string S, pre-process the S to make a new S' w/o space }
{Algo:
First check if the string S is already a palindrome - mirror test (Ci==Cn-1-i, i=0 to n/2)
If Yes, the shortest length is S's length. i.e. n
If No, find the minimum addition to make it a palindrome:
Use the ith char as pivot (i = (n/2-1) to 0)
If S' left part is the mirror of S's right part with the ith char as pivot (Cj==Ci+i-j)
the minimum addition is: delta = (n-2*i-1) and thus the shortest length=n+delta=2*n-2*i-1
return the shortest length
Note: if want to ignore space in the string S, pre-process the S to make a new S' w/o space }
It's easy to get a O(n) solution. We only need to find the length of first k characters that it's already satisfy palindrome.
Just think about KMP.
Here is the solution:
1. String s = origin + reverse(origin);
2. make next[] array of s in KMP algorithm. Then next[s.length] will be the k.
3. return origin.length - k
For example:
The origin string is abacd, then s=abacddcaba, then next[s.length] will be 3.
c#.
static private string MakePalindrome( string str ) {
int index = 0;
bool matchFound = true;
for( int i = str.Length - 1; i >= 0; i-- ) {
int k = i; int j = 0;
while( k >= 0 ) {
if( str[ j ] != str[ k ] ) {
matchFound = false; break;
}
k--; j++;
}
if( matchFound ) { index = j; break; }
matchFound = true;
}
var res = new StringBuilder();
foreach ( var ch in str.Substring( index ).Reverse() ) {
res.Append( ch );
}
return res.Append( str ).ToString();
}
#include<iostream>
#include <list>
using namespace std;
void makePalindrome(char arr[],int len)
{
int front=0, end=len-1;
char result[100];
int i=0;
while(front != end)
{
if( arr[front] == arr[end])
{
front++;
end--;
}
else
{
result[i]=arr[end];
i++;
end--;
}
}
result[i]='\0';
//printing the result for test
i=0;
while(result[i] != '\0')
cout<<result[i++];
i=0;
while(arr[i] != '\0')
cout<<arr[i++];
}
int main()
{
char a[]="racecarart";
makePalindrome(a,10);
return 1;
}
Naive approach :( O(n^2)
public class PalindromeAddFront{
public static void main(String[] args){
String str = "racexyzart";
int length = lengthToMakePalindrome(str);
StringBuilder sbr = new StringBuilder(str.substring(str.length() - length));
sbr.reverse().append(str);
System.out.println(sbr);
}
public static int lengthToMakePalindrome(String str){
int i = 0, j = str.length() - 1;
int count = 0;
while(i < j){
if(str.charAt(i) == str.charAt(j)){
i++;
j--;
}else{
j += (i - 1);
i = 0;
count++;
}
}
return count;
}
}
The thing is, the time complexity gets reduced by simply finding palindrome that start from first character. If we reduce the suffix tree implementation:
- CT November 21, 20141. Create suffix tree from the reverse string (Ukkonen proved this is O(n))
2. Walk this tree from the beginning with the original string until there is path.
This is largest palindrome that starts with beginning. So you need to add [original string length] - [found polyndrome] characters in the front