Dota virkne, kurā ir daži mazie alfabēta rakstzīmes un viens īpašās rakstzīmes punkts (.). Mums ir jāaizstāj visi punkti ar kādu alfabēta rakstzīmi tā, lai iegūtā virkne kļūtu par palindromu daudzu iespējamo nomaiņu gadījumā, mums jāizvēlas leksikogrāfiski mazākā palindroma virkne. Ja nav iespējams pārvērst virkni palindromā pēc visām iespējamām nomaiņām, izvade nav iespējama.
Piemēri:
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
Mēs varam atrisināt šo problēmu šādi. Tā kā iegūtajai virknei ir jābūt palindromai, mēs varam pārbaudīt bezpunktu rakstzīmju pāri pašā sākumā, ja tie nesakrīt, tad tiešā atgriešana nav iespējama, jo mēs varam ievietot jaunu rakstzīmi tikai punktu pozīcijā, nevis citur.
Pēc tam mēs atkārtojam virknes rakstzīmes, ja pašreizējā rakstzīme ir punkts, tad pārbaudām tās pāra rakstzīmi (rakstzīme (n - i -1) pozīcijā), ja šī rakstzīme ir arī punkts, tad mēs varam aizstāt abas rakstzīmes ar "a", jo "a" ir mazākais mazais alfabēts, kas garantēs mazāko leksikogrāfisko virkni beigās, aizvietojot abas ar jebkuru citu rakstzīmi, tiks iegūta lielāka virkne. Citā gadījumā, ja pārī savienotā rakstzīme nav punkts, tad, lai izveidotu virknes palindromu, pašreizējā rakstzīme ir jāaizstāj ar tās pāra rakstzīmi.
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
Iepriekš minētā procedūra dod mums leksikogrāfiski mazāko palindromu virkni.
Īstenošana:
C++// C++ program to get lexicographically smallest // palindrome string #include
// 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 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# 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 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 ?> <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>
Izvade
abcaeacba
Laika sarežģītība: O(n) kur n ir virknes garums.
Papildtelpas sarežģītība: O(1)