Home » Interview Questions » String Interview Questions » Smallest palindrome after replacement

Smallest palindrome after replacement


()

Given input string contains lower case alphabets characters and dots(.). We need to replace all dots with some alphabet character in such a way that resultant string becomes a palindrome.

The palindrome should be lexicographically smallest.

Examples

a) Input string : “a..b.a”
Output : aabbaa
This is the smallest palindrome possible.

b) Input string : “a..b.c”
Output : Not possible
With given string we cannot form palindrome.

Time complexity : O(n)

Algorithm

1. Check pair of non-dot characters ignoring dot characters.

a. If left and right are both non-dots and not equal return false.
b. Else, traverse till mid.
c. Return True, if it reaches end.

2. If both ‘i’ and ‘n-i-1’ positions are dots replace them with ‘a’.

3. Else, if one of them is dot character replace that by other non-dot character.

4. Return the final string.

C++ Program

#include <bits/stdc++.h>

using namespace std;
 
//Function to check if input string can form palindrome or not
bool CanFormPalindrome(string input_string)
{
    int length = input_string.length();
    for (int i=0; i<length/2; i++)
    {
        if (input_string[i] != '.' && input_string[length-i-1] != '.' && input_string[i] != input_string[length-i-1])
        {
            return false;
        }
    }
    return true;
}
 
string SmallestPalindrome(string input_string)
{
    //Check if input string can form palindrome or not
    //If not return Not Possible
    if (!CanFormPalindrome(input_string))
    {
        return "Not Possible";
    }
    //Traverse the input string
    //If both ‘i’ and ‘n-i-1’ positions are dots replace them with ‘a’.
    //If one of them is dot character replace that by other non-dot character.
    int length = input_string.length();
    for (int i = 0; i < length; i++)
    {
        if (input_string[i] == '.')
        {
            if (input_string[length - i - 1] != '.')
            {
                input_string[i] = input_string[length - i - 1];
            }
            else
            {
                input_string[i] = input_string[length - i - 1] = 'a';
            }
        }
    }
    //Return the final string.
    return input_string;
}
 
//Main function
int main()
{
    string input_string = "a..b.a";
    cout<<"Output palindrome string is: "<<SmallestPalindrome(input_string)<<endl;
    return 0;
}

Try It

READ  Valid Parentheses

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions