Problem: Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
Example:
Input: "aabb" Output: ["abba", "baab"]
Input: "abc" Output: []
Approach: We are using hashmap to store the frequency of each character of the given string. We know that if there are more than one character exist with odd frequency than there will be no palindrome permutation of the given string.
If we find a character with odd frequency then we also know that it has to be in the middle of any palindrome permutation. With this understanding we will generate all the palindromic permutation of the string s with the help of the hashmap.
Implementation in C#:
public static List<string> GeneratePalindromes(string s)
{
int length = s?.Length ?? 0;
List<string> result = new List<string>();
if (length == 0)
{
return result;
}
int[] charFreqMap = new int[26];
foreach (char ch in s)
{
++charFreqMap[ch - 'a'];
}
bool isOddFreqCharFound = false;
int oddIndex = -1;
for (int i = 0; i < 26; ++i)
{
if (charFreqMap[i] % 2 == 1)
{
if (isOddFreqCharFound)
{
return result;
}
isOddFreqCharFound = true;
oddIndex = i;
}
}
string currResult = "";
if (isOddFreqCharFound)
{
currResult += ((char)(oddIndex + 'a')).ToString();
--charFreqMap[oddIndex];
}
GetPalindromePermutation(charFreqMap, currResult, result, length);
return result;
}
private static void GetPalindromePermutation(int[] charFreqMap, string currResult, List<string> result, int maxLength)
{
if (currResult.Length == maxLength)
{
result.Add(currResult);
return;
}
for (int i = 0; i < charFreqMap.Length; ++i)
{
if (charFreqMap[i] > 0)
{
charFreqMap[i] -= 2;
char ch = (char)(i + 'a');
GetPalindromePermutation(charFreqMap, ch + currResult + ch, result, maxLength);
charFreqMap[i] += 2;
}
}
}
Complexity: ??
No comments:
Post a Comment