# Smallest Palindrome after Replacement  Difficulty Level Easy
Palindrome String

## Problem Statement  In the “Smallest Palindrome after Replacement” problem we have given the input string contains lower case alphabets characters and dots(.). We need to replace all dots with some alphabet character in such a way that the resultant string becomes a palindrome. The palindrome should be lexicographically smallest.

## Input Format  The first and only one line containing the input string s.

## Output Format  Print the smallest lexicographic string which is a palindrome. If no such string formed then print “Not possible”.

## Constraints  • 1<=|s|<=10^6
• s[i] is lower case alphabets characters or dot”.”

## Example  `a..b.a`
`aabbaa`

Explanation: For this string, the smallest palindrome is “aabbaa”. Here we replace s[i] and s[n-1-i] with ‘a’ if both the char are dot(.). If one of them is a dot character replace that with another non-dot character.

`a..b.c`
`Not possible`

Explanation: In this string, we can easily see the first and last char are not the same so we can’t make this string into a palindrome string. So, we print the answer as “Not possible”.

## Algorithm for Smallest Palindrome after Replacement  1. Check pair of non-dot characters ignoring dot characters.

•  If left and right are both non-dots and not equal then return False.
• Else, traverse till mid.
• Return True, if it reaches the end.
Reverse individual words

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

3. Else, if one of them is a dot character replace that with another non-dot character.

4. Return the final string.

## Implementation  ### C++ program for Smallest Palindrome after Replacement

```#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin>>s;
int n=s.length();
int flag=0;
for(int i=0;i<n/2;i++)
{
if(s[i]!='.' && s[n-1-i]!='.' && s[i]!=s[n-1-i])
{
flag=1;
break;
}
}
if(flag==1)
{
cout<<"Not possible"<<endl;
}
else
{
for(int i=0;i<n;i++)
{
if(s[i]=='.')
{
if(s[n-1-i]=='.')
{
s[i]='a';
s[n-1-i]='a';
}
else
{
s[i]=s[n-1-i];
}
}
}
cout<<s<<endl;
}
return 0;
}```

### Java program for Smallest Palindrome after Replacement

```import java.util.Scanner;

class sum {

public static void main(String[] args)
{
Scanner sr= new Scanner(System.in);
String s = sr.next();
int n = s.length();
char a[] = s.toCharArray();
int flag=0;
for(int i=0;i<n/2;i++)
{
if(a[i]!='.' && a[n-1-i]!='.' && a[i]!=a[n-1-i])
{
flag=1;
break;
}
}
if(flag==1)
{
System.out.println("Not possible");
}
else
{
for(int i=0;i<n;i++)
{
if(a[i]=='.')
{
if(a[n-1-i]=='.')
{
a[i]='a';
a[n-1-i]='a';
}
else
{
a[i]=a[n-1-i];
}
}
}
for(int i=0;i<n;i++)
{
System.out.print(a[i]);
}
System.out.println();
}
}
}```
`a..b.a`
`aabbaa`

## Complexity Analysis for Smallest Palindrome after Replacement  ### Time Complexity

O(n) where n is the size of the given string “s”. Here we just traverse the given string and perform some useful tasks.

### Space Complexity

O(1) because we don’t use any extra space here. Which leads us to constant space complexity.