# 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;
}``````

Scroll to Top