Smallest Palindrome after Replacement

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.

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.