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

 


Next > < Prev
Scroll to Top