I'm trying to come up with an algorithm for calculating the number of palindromes of different strings formed out of the characters of a parent string
Right now I'm using the following to test if the string generated is a palindrome:
public static Boolean isPalindrome(String s)
{
int n = s.length();
for (int i=0;i<(n / 2);++i)
{
if (s.charAt(i) != s.charAt(n - i - 1))
{
return false;
}
}
return true;
}
Which is working properly, however any attempt I've made to create a palindrome is not working the way I'd like. Basically I want to take a word like racecar and come up with all palindromes that are possible with any combination of any char in the string as long as it's a palindrome. So for example, with racecar of course racecar would work as well as aaacaaa or even eecrcee. I've been futile in my attempts, has anyone ever tried generating palindromes based off of a string with these constraints?
The number of possible palindromes depends on how many characters you can choose from, and how long the word has to be.
In the "racecar" example, you have 4 unique letters to choose from, and you need to make a string of length 7. So there are 4 choices for the 1st character, 4 for the 2nd, 4 for the 3rd, 4 for the 4th (middle character). The 5th character must be the same as the 3rd, the 6th must be the same as the 2nd, and the 7th must be the same as 1st.
You only need to make a letter choice for half of the string (in this case, the first 4 letters), because in a palindrome the other half is a mirror image of the first half. So 4*4*4*4 possibilities in total for this example.
In general, it will be N^K (Math.pow(N, K)) possible palindromes, where N is the number of distinct letters you can choose from, and K is half the length of the string you need (add 1 if the string length is odd).