Найдите две уникальные строки палиндрома, используя заданные символы строки

Вам на вход дана строка S из двух различных символов , задача состоит в том, чтобы найти две строки, используя символы данной строки, такие, что обе строки отличны от S и обе должны быть палиндромом.

Примеры:

Input: S = “xyyxxxx”
Output: yxxxxxy, xxyxyxx
Explanation: It can be verified that at least one of the output strings is different from S and both are palindrome.

Input: S=”ab”      
Output: Not Possible

Подход: Реализуйте идею ниже, чтобы решить проблему:

The problem is observation based and can be solved via checking parity and frequency of both distinct characters in S. Below are the some observations by which we can conclude some rules. Considered X, Y are the frequencies of two distinct charcaters in S: 

1. If the below conditions are satisfied, it can be verified that there will not be any two palindrome strings satisfying given conditions:
   • If any of X or Y is equal to 1.
   • Both X and Y are Odd.
2. Rest of the cases except discussed above will have a guaranteed solution.
   • When Both X and Y are even: 
     Say X = 4, Y = 6 then two possible strings are “aabbbbbbaa” and “bbbaaaabbb” and both are differents.
   • When either X or Y is odd:
     Say X = 3, Y = 6 then two possible strings are “bbbaaabbb” and “abbbabbba“.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Проверьте четность X и Y , т. е. двух разных символов.
• Выведите ответ в соответствии с указанным выше соотношением X и Y.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(1)