Make lexicographically smallest palindrome by substituting missing characters
Given a string str some of whose characters are missing and are represented by a ‘*’. The task is to substitute the missing characters so as to make the lexicographically smallest palindrome. If it ot possible to make the string palindrome then print -1.
Examples:
Input: str = “ab*a”
Output: abba
Input: a*b
Output: -1
We can’t make it palindrome so output is -1.
Approach:
- Place the ‘i’ marker at the starting of string and ‘j’ marker at the end of the string.
- If characters at both the positions are missing then substitute both the characters with ‘a’ so as to make it lexicographically smallest palindrome.
- If character at only ith or jth position is missing then replace it with jth or ith character respectively.
- If character at ith and jth positions are not equal then the string cannot be made into a palindrome and print -1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the lexicographically // smallest palindrome that can be made from // the given string after replacing // the required characters string makePalindrome(string str) { int i = 0, j = str.length() - 1; while (i <= j) { // If characters are missing at both the positions // then substitute it with 'a' if (str[i] == '*' && str[j] == '*' ) { str[i] = 'a' ; str[j] = 'a' ; } // If only str[j] = '*' then update it // with the value at str[i] else if (str[j] == '*' ) str[j] = str[i]; // If only str[i] = '*' then update it // with the value at str[j] else if (str[i] == '*' ) str[i] = str[j]; // If characters at both positions // are not equal and != '*' then the string // cannot be made palindrome else if (str[i] != str[j]) return "-1" ; i++; j--; } // Return the required palindrome return str; } // Driver code int main() { string str = "na*an" ; cout << makePalindrome(str); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the lexicographically // smallest palindrome that can be made from // the given string after replacing // the required characters static String makePalindrome( char [] str) { int i = 0 , j = str.length - 1 ; while (i <= j) { // If characters are missing at both the positions // then substitute it with 'a' if (str[i] == '*' && str[j] == '*' ) { str[i] = 'a' ; str[j] = 'a' ; } // If only str[j] = '*' then update it // with the value at str[i] else if (str[j] == '*' ) str[j] = str[i]; // If only str[i] = '*' then update it // with the value at str[j] else if (str[i] == '*' ) str[i] = str[j]; // If characters at both positions // are not equal and != '*' then the string // cannot be made palindrome else if (str[i] != str[j]) return "-1" ; i++; j--; } // Return the required palindrome return String.valueOf(str); } // Driver code public static void main(String[] args) { char [] str = "na*an" .toCharArray(); System.out.println(makePalindrome(str)); } } /* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of the approach # Function to return the lexicographically # smallest palindrome that can be made from # the given string after replacing # the required characters def makePalindrome(str1): i = 0 j = len (str1) - 1 str1 = list (str1) while (i < = j): # If characters are missing # at both the positions # then substitute it with 'a' if (str1[i] = = '*' and str1[j] = = '*' ): str1[i] = 'a' str1[j] = 'a' # If only str1[j] = '*' then update it # with the value at str1[i] elif (str1[j] = = '*' ): str1[j] = str1[i] # If only str1[i] = '*' then update it # with the value at str1[j] elif (str1[i] = = '*' ): str1[i] = str1[j] # If characters at both positions # are not equal and != '*' then the string # cannot be made palindrome elif (str1[i] ! = str1[j]): str1 = '' . join(str1) return "-1" i + = 1 j - = 1 # Return the required palindrome str1 = '' . join(str1) return str1 # Driver code if __name__ = = '__main__' : str1 = "na*an" print (makePalindrome(str1)) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of the approach using System; class GFG { // Function to return the lexicographically // smallest palindrome that can be made from // the given string after replacing // the required characters static String makePalindrome( char [] str) { int i = 0, j = str.Length - 1; while (i <= j) { // If characters are missing at both the positions // then substitute it with 'a' if (str[i] == '*' && str[j] == '*' ) { str[i] = 'a' ; str[j] = 'a' ; } // If only str[j] = '*' then update it // with the value at str[i] else if (str[j] == '*' ) str[j] = str[i]; // If only str[i] = '*' then update it // with the value at str[j] else if (str[i] == '*' ) str[i] = str[j]; // If characters at both positions // are not equal and != '*' then the string // cannot be made palindrome else if (str[i] != str[j]) return "-1" ; i++; j--; } // Return the required palindrome return String.Join( "" ,str); } // Driver code public static void Main(String[] args) { char [] str = "na*an" .ToCharArray(); Console.WriteLine(makePalindrome(str)); } } // This code has been contributed by 29AjayKumar |
PHP
<?php // PHP implementation of the approach // Function to return the lexicographically // smallest palindrome that can be made from // the given string after replacing // the required characters function makePalindrome( $str ) { $i = 0; $j = strlen ( $str ) - 1; while ( $i <= $j ) { // If characters are missing at both the positions // then substitute it with 'a' if ( $str [ $i ] == '*' && $str [ $j ] == '*' ) { $str [ $i ] = 'a' ; $str [ $j ] = 'a' ; } // If only str[j] = '*' then update it // with the value at str[i] else if ( $str [ $j ] == '*' ) $str [ $j ] = $str [ $i ]; // If only str[i] = '*' then update it // with the value at str[j] else if ( $str [ $i ] == '*' ) $str [ $i ] = $str [ $j ]; // If characters at both positions // are not equal and != '*' then the string // cannot be made palindrome else if ( $str [ $i ] != $str [ $j ]) return "-1" ; $i ++; $j --; } // Return the required palindrome return $str ; } // Driver code $str = "na*an" ; echo makePalindrome( $str ); // This Code is contributed by AnkitRai01 ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the lexicographically // smallest palindrome that can be made from // the given string after replacing // the required characters function makePalindrome(str) { var i = 0, j = str.length - 1; while (i <= j) { // If characters are missing at both the positions // then substitute it with 'a' if (str[i] == '*' && str[j] == '*' ) { str[i] = 'a' ; str[j] = 'a' ; } // If only str[j] = '*' then update it // with the value at str[i] else if (str[j] == '*' ) str[j] = str[i]; // If only str[i] = '*' then update it // with the value at str[j] else if (str[i] == '*' ) str[i] = str[j]; // If characters at both positions // are not equal and != '*' then the string // cannot be made palindrome else if (str[i] != str[j]) return "-1" ; i++; j--; } // Return the required palindrome return str.join( "" ); } // Driver code var str = "na*an" .split( '' ); document.write(makePalindrome(str)); </script> |
Output:
naaan
Time Complexity: O(n), where n is the length of the given string.
Auxiliary Space: O(1), no extra space is required, so it is a constant.