CareerCup

step1 : This problem can solved just by finding permutations of a,e,i,o,u in 5 places ( repetition allowed )

step2: divide 10 place into two parts. find permutations for first 5 places, and fill remaining 5 places in reverse order.

Step3: print 10 places at the end of each permutation . total palindromes 5*5*5*5*5

code ::

//calling convention permutations( input, permute, 5, 0);

void permutations(char Input[], char permute[], int n, int index )
{
int i=0;
// printing palindrome
if( index == n )
{
for( i =0 ;i < n; i++ )
printf("%d, ", Permute[i] );
for( i =n-1 ;i >= 0; i--)
printf("%d, ", Permute[i] );
Printf("\n");

return ;
}

for (i = 0 ; i < n; i++)
{
Permute[index] = Input[i];

permutations( Input, permute, n, index +1 );
}

}

Good questions. A recursion approach would probably be easiest to implement it. The complexity of the algorithm depends on two variables, size of the alphabet set n and size of resulting palindromes k. If n=5 and k=3 then we would be expected to come up with results such as:

aaa
aea
aia
aoa
aua
eae
...

so three postions, half them will have k choices each, the other half will depend on choices made in the first half

for n=5, k=5, the structure could look like:

n n n 1 1 -> total number of palindromes with be O(n^3) or to generalize O(n^(k/2))

public static void palindromes(char[] letters, int k, int position, char[] str, Set<String> result) {
        for(char c : letters) {
            char[] str_copy = str.clone();
            str_copy[position] = c;
            str_copy[(k-1)-position] = c;
            if(position == k/2) {
                // finished
                result.add(new String(str_copy));
            } else {
                palindromes(letters, k, position+1, str_copy, result);
            }
        }
    }

great insight siva sai
code in python

def permutations(alp,n):
if n==0: return [""]
lower=permutations(alp,n-1)
res=[]
for a in alp:
for low in lower:
res.append(a+low)
return res

def palindrome(alp,n):
num=0
if n%2==0:
num=n/2
else:
num=n/2+1

complete=permutations(alp,num)
if n%2==0:
for perm in complete:
print perm+perm[::-1]
else:
for perm in complete:
print perm+perm[:-1][::-1]

great insight siva sai
code in python

def permutations(alp,n):
if n==0: return [""]
lower=permutations(alp,n-1)
res=[]
for a in alp:
for low in lower:
res.append(a+low)
return res

def palindrome(alp,n):
num=0
if n%2==0:
num=n/2
else:
num=n/2+1

complete=permutations(alp,num)
if n%2==0:
for perm in complete:
print perm+perm[::-1]
else:
for perm in complete:
print perm+perm[:-1][::-1]

Two cases
odd size and even size.
odd size --> center is a single letter e.g. size = 5 , palindrome = madam .. center = d
even size --> center is a double letter e.g. size = 6, palindrome = maddam.. center = dd
(Counter Examples welcome)

So if odd, add the first letter in the char set once and expand around the center.
e.g. Input Set (a,b) , size = 3 . Start with a --> aaa --> bab
Then b --> aba --> bbb
Similarly, for even sized Palindrome
e.g. Input Set (a,b) size = 4, Start with aa instead of a.
aa --> aaaa --> baab
come back to next char i.e. b .. start with bb --> abba --> bbbb

here is the java code for this implementation

public static ArrayList<String> sizeKPalindromes(ArrayList<Character> charSet, int size) {
		Boolean odd = false;
		if ( (size & 1) > 0 ) {/* odd */
			odd = true;
		}
		return sizeKPalindromes("", charSet, size,odd);
		
		
	}

	private static ArrayList<String> sizeKPalindromes(String string, ArrayList<Character> charSet, int size, Boolean odd) {
		if (string == null) {
			return null;
		}
		
		if (string.length() == size) {
			ArrayList<String> currPalindrome = new ArrayList<String>();
			currPalindrome.add(string);
			return currPalindrome;
		}
		
		ArrayList<String> allPalindromeStrings = new ArrayList<String>();
		
		for (int i = 0; i < charSet.size(); i++) {
			
			String tempString = new String();
			
			if (odd && string.isEmpty()) {
				tempString = string + charSet.get(i);
			}
			
			else {
				tempString = charSet.get(i) + string + charSet.get(i);
			}
			
			ArrayList<String> tempPalindromes = sizeKPalindromes(tempString, charSet, size, odd);
			allPalindromeStrings.addAll(tempPalindromes);
		}
		
		
		
		
		return allPalindromeStrings;
		
	}

@dilip.rangarajan
Can you please explain your code? I am unable to understand how it works according to your above stated algo

The point is if the string is "ABCD" and k =5,
then we need to fix the middle position for each character..
1.palindrome[2]='A',
now we should find all possible 2 character sets to fill palindrome[0] and palindrome[1] and reverse it in 3 and 4 indices..

Or expand around center by prefixing and suffixing the same character.
E.g. a --> aaa or a-->bab

Or expand around center by prefixing and suffixing the same character.
E.g. a --> aaa or a-->bab

char *s = {a,b,c,d}; // the set
int cs = 4; // the size of the set

void f(int n)
{
   char *a = new char[n+1]; // buf for storing the chars
   a[n] = '\0';
  
   f1(a,floor(n/2),n);
}

void f1(char* a, int x, int n)
{
    for(int i=0;i<cs;++i)
    {
         a[x]=a[n-1-x]=s[i];

         if(x==0)
         {
            printf("%s\n", a); 
         }
         else
         {
            f1(a, x-1, n);
         }
    }   
}

ok.