Palindromo più piccolo dopo la sostituzione
Data una stringa che contiene alcuni caratteri alfabetici minuscoli e un carattere speciale punto (.). Dobbiamo sostituire tutti i punti con qualche carattere alfabetico in modo tale che la stringa risultante diventi un palindromo. In caso di molte possibili sostituzioni, dobbiamo scegliere la stringa palindroma che è lessicograficamente più piccola. Se non è possibile convertire la stringa in palindromo dopo tutte le possibili sostituzioni, l'output è Not possible.
Esempi:
Input : str = ab..e.c.a Output : abcaeacba The smallest palindrome which can be made after replacement is 'abcaeacba' We replaced first dot with 'c' second dot with 'a' third dot with 'a' and fourth dot with 'b' Input : str = ab..e.c.b Output : Not Possible It is not possible to convert above string into palindrome
Possiamo risolvere questo problema come segue Poiché la stringa risultante deve essere palindroma, possiamo controllare una coppia di caratteri non punto all'inizio se non corrispondono, quindi il ritorno diretto non è possibile perché possiamo posizionare il nuovo carattere solo nella posizione dei punti e non altrove.
Dopodiché iteriamo sui caratteri della stringa se il carattere corrente è un punto, quindi controlliamo il suo carattere accoppiato (carattere nella (n – i -1)esima posizione) se anche quel carattere è un punto, possiamo sostituire entrambi i caratteri con "a" perché "a" è l'alfabeto minuscolo più piccolo che garantirà la stringa lessicografica più piccola alla fine, sostituendo entrambi con qualsiasi altro carattere si otterrà una stringa palindromica lessicograficamente più grande. In altri casi, se il carattere accoppiato non è un punto, per rendere la stringa palindroma dobbiamo sostituire il carattere corrente con il suo carattere accoppiato.
So in short If both 'i' and 'n- i- 1' are dot replace them by ‘a’ If one of them is a dot character replace that by other non-dot character
La procedura sopra ci fornisce la stringa palindromo lessicograficamente più piccola.
Attuazione:
C++ // C++ program to get lexicographically smallest // palindrome string #include using namespace std ; // Utility method to check str is possible palindrome // after ignoring . bool isPossiblePalindrome ( string str ) { int n = str . length (); for ( int i = 0 ; i < n / 2 ; i ++ ) { /* If both left and right character are not dot and they are not equal also then it is not possible to make this string a palindrome */ if ( str [ i ] != '.' && str [ n - i -1 ] != '.' && str [ i ] != str [ n - i -1 ]) return false ; } return true ; } // Returns lexicographically smallest palindrom // string if possible string smallestPalindrome ( string str ) { if ( ! isPossiblePalindrome ( str )) return 'Not Possible' ; int n = str . length (); // loop through character of string for ( int i = 0 ; i < n ; i ++ ) { if ( str [ i ] == '.' ) { // if one of character is dot replace dot // with other character if ( str [ n - i - 1 ] != '.' ) str [ i ] = str [ n - i - 1 ]; // if both character are dot then replace // them with smallest character 'a' else str [ i ] = str [ n - i - 1 ] = 'a' ; } } // return the result return str ; } // Driver code to test above methods int main () { string str = 'ab..e.c.a' ; cout < < smallestPalindrome ( str ) < < endl ; return 0 ; }
Java // Java program to get lexicographically // smallest palindrome string class GFG { // Utility method to check str is // possible palindrome after ignoring static boolean isPossiblePalindrome ( char str [] ) { int n = str . length ; for ( int i = 0 ; i < n / 2 ; i ++ ) { /* If both left and right character are not dot and they are not equal also then it is not possible to make this string a palindrome */ if ( str [ i ] != '.' && str [ n - i - 1 ] != '.' && str [ i ] != str [ n - i - 1 ] ) return false ; } return true ; } // Returns lexicographically smallest // palindrome string if possible static void smallestPalindrome ( char str [] ) { if ( ! isPossiblePalindrome ( str )) System . out . println ( 'Not Possible' ); int n = str . length ; // loop through character of string for ( int i = 0 ; i < n ; i ++ ) { if ( str [ i ] == '.' ) { // if one of character is dot // replace dot with other character if ( str [ n - i - 1 ] != '.' ) str [ i ] = str [ n - i - 1 ] ; // if both character are dot // then replace them with // smallest character 'a' else str [ i ] = str [ n - i - 1 ] = 'a' ; } } // return the result for ( int i = 0 ; i < n ; i ++ ) System . out . print ( str [ i ] + '' ); } // Driver code public static void main ( String [] args ) { String str = 'ab..e.c.a' ; char [] s = str . toCharArray (); smallestPalindrome ( s ); } } // This code is contributed // by ChitraNayal
Python 3 # Python 3 program to get lexicographically # smallest palindrome string # Utility method to check str is # possible palindrome after ignoring def isPossiblePalindrome ( str ): n = len ( str ) for i in range ( n // 2 ): # If both left and right character # are not dot and they are not # equal also then it is not possible # to make this string a palindrome if ( str [ i ] != '.' and str [ n - i - 1 ] != '.' and str [ i ] != str [ n - i - 1 ]): return False return True # Returns lexicographically smallest # palindrome string if possible def smallestPalindrome ( str ): if ( not isPossiblePalindrome ( str )): return 'Not Possible' n = len ( str ) str = list ( str ) # loop through character of string for i in range ( n ): if ( str [ i ] == '.' ): # if one of character is dot # replace dot with other character if ( str [ n - i - 1 ] != '.' ): str [ i ] = str [ n - i - 1 ] # if both character are dot # then replace them with # smallest character 'a' else : str [ i ] = str [ n - i - 1 ] = 'a' # return the result return str # Driver code if __name__ == '__main__' : str = 'ab..e.c.a' print ( '' . join ( smallestPalindrome ( str ))) # This code is contributed by ChitraNayal
C# // C# program to get lexicographically // smallest palindrome string using System ; public class GFG { // Utility method to check str is // possible palindrome after ignoring static bool isPossiblePalindrome ( char [] str ) { int n = str . Length ; for ( int i = 0 ; i < n / 2 ; i ++ ) { /* If both left and right character are not dot and they are not equal also then it is not possible to make this string a palindrome */ if ( str [ i ] != '.' && str [ n - i - 1 ] != '.' && str [ i ] != str [ n - i - 1 ]) return false ; } return true ; } // Returns lexicographically smallest // palindrome string if possible static void smallestPalindrome ( char [] str ) { if ( ! isPossiblePalindrome ( str )) Console . WriteLine ( 'Not Possible' ); int n = str . Length ; // loop through character of string for ( int i = 0 ; i < n ; i ++ ) { if ( str [ i ] == '.' ) { // if one of character is dot // replace dot with other character if ( str [ n - i - 1 ] != '.' ) str [ i ] = str [ n - i - 1 ]; // if both character are dot // then replace them with // smallest character 'a' else str [ i ] = str [ n - i - 1 ] = 'a' ; } } // return the result for ( int i = 0 ; i < n ; i ++ ) Console . Write ( str [ i ] + '' ); } // Driver code public static void Main () { String str = 'ab..e.c.a' ; char [] s = str . ToCharArray (); smallestPalindrome ( s ); } } // This code is contributed by PrinciRaj1992
PHP // PHP program to get lexicographically // smallest palindrome string // Utility method to check str is // possible palindrome after ignoring function isPossiblePalindrome ( $str ) { $n = strlen ( $str ); for ( $i = 0 ; $i < $n / 2 ; $i ++ ) { /* If both left and right character are not dot and they are not equal also then it is not possible to make this string a palindrome */ if ( $str [ $i ] != '.' && $str [ $n - $i - 1 ] != '.' && $str [ $i ] != $str [ $n - $i - 1 ]) return false ; } return true ; } // Returns lexicographically smallest // palindrome string if possible function smallestPalindrome ( $str ) { if ( ! isPossiblePalindrome ( $str )) return 'Not Possible' ; $n = strlen ( $str ); // loop through character of string for ( $i = 0 ; $i < $n ; $i ++ ) { if ( $str [ $i ] == '.' ) { // if one of character is dot // replace dot with other character if ( $str [ $n - $i - 1 ] != '.' ) $str [ $i ] = $str [ $n - $i - 1 ]; // if both character are dot // then replace them with // smallest character 'a' else $str [ $i ] = $str [ $n - $i - 1 ] = 'a' ; } } // return the result return $str ; } // Driver code $str = 'ab..e.c.a' ; echo smallestPalindrome ( $str ); // This code is contributed // by ChitraNayal ?>
JavaScript < script > // Javascript program to get lexicographically // smallest palindrome string // Utility method to check str is // possible palindrome after ignoring function isPossiblePalindrome ( str ) { let n = str . length ; for ( let i = 0 ; i < Math . floor ( n / 2 ); i ++ ) { /* If both left and right character are not dot and they are not equal also then it is not possible to make this string a palindrome */ if ( str [ i ] != '.' && str [ n - i - 1 ] != '.' && str [ i ] != str [ n - i - 1 ]) return false ; } return true ; } // Returns lexicographically smallest // palindrome string if possible function smallestPalindrome ( str ) { if ( ! isPossiblePalindrome ( str )) document . write ( 'Not Possible' ); let n = str . length ; // loop through character of string for ( let i = 0 ; i < n ; i ++ ) { if ( str [ i ] == '.' ) { // if one of character is dot // replace dot with other character if ( str [ n - i - 1 ] != '.' ) str [ i ] = str [ n - i - 1 ]; // if both character are dot // then replace them with // smallest character 'a' else str [ i ] = str [ n - i - 1 ] = 'a' ; } } // return the result for ( let i = 0 ; i < n ; i ++ ) document . write ( str [ i ] + '' ); } // Driver code let str = 'ab..e.c.a' ; let s = str . split ( '' ); smallestPalindrome ( s ); // This code is contributed by rag2127 < /script>
Produzione
abcaeacba
Complessità temporale: O(n) dove n è la lunghezza della stringa.
Complessità dello spazio ausiliario: O(1)
