CareerCup

I will post the code for this shortly, but here is the explanation in English:

1. You will need a suffix array (you can use a suffix tree, but suffix array takes up less space and is easier to build, especially on a board during the interview).

2. You will need to build two suffix arrays - one for your string: S and one for the reverse of S'. O(n) time

3. Sort the suffixes in the suffix array O(n lg n) time

4. Now run a simple loop comparing the first, second, third.... n elements of your suffix array. Remember, you are not comparing each element to every element. You are just incrementing a single index - 'i' and comparing the element at 'i' in the first suffix array, with that of the second suffix array - O(n) time

5. When you compare, you are actually trying to find the Longest Common Prefix. Suffix arrays naturally lets you perform this operation - O(k) time, where k is the length of the longest common prefix. Since you run this for every compare (in Step 4), total time is O(nk)

6. If the length of the LCP at each compare is greater than 2, then you have a palindrome :)
{{

8. Go back to Step 4 and repeat till you have scanned all elements of both the suffix arrays.

9. Simply output whatever you stored in Step 7 and you have a list of palindromes :)

I am not going to explain how or why suffix arrays/trees are able to do this. I suggest you go through a good suffix array article online (especially once Wikipedia stops protesting against SOPA :P)

I will post the code for this shortly - maybe tomorrow.

anagram or palimdron? you confused me

i guess it should be palandrome

Use a stack

"dadana" may be question is not cleared to me but what u say palindrome then dadana string will have 6 palindromes withint pallindromes are
1. a
2. d
3. n
4. ana
5.dad
6.ada
if ia am wrong please tell me what is correct question confussing me.

O(n^2) simple solution for all palindromes. Take matrix( (len(s)+1)*(len(s1)+1)) arrange s on the first row, reverse s(call it rs) arrange it in the first column. Populate matrix with 0 or 1 accordingly. Count all diagonals whose length is more than 1 ,this gives all possible palindromes.

If its just about checking for palindromes then the following code works for me:

public class anagram {
  public static void main(String[] args) {
    String s1 = "nitin";
    String s2 = "MALAYALAM";
    String s3 = "abba";
    String s4 = "aa";
    String s5 = "haha";    
    System.out.println("Result for s1 is: " +anagramtest(s1));
    System.out.println("Result for s2 is: " +anagramtest(s2));
    System.out.println("Result for s3 is: " +anagramtest(s3));
    System.out.println("Result for s4 is: " +anagramtest(s4));
    System.out.println("Result for s5 is: " +anagramtest(s5));
  }
  
  public static boolean anagramtest(String s) {
    boolean flag = false;
    char[] c = s.toCharArray();
    if(s.length() == 2) {
    	if(c[0] == c[1]) { flag = true; }
    }
    else if(s.length() > 2) {
    	for (int start = 0, finish = s.length()-1; start < finish; start++,finish--) {
    		if(c[start] == c[finish]) {
    			flag = true;
    		}    		
    	}
    }
    return flag;
  }
}

But i think the question is asking for palindromes within palindromes essentially asking us to count the total palindromes within a given word. Please clarify.

From above comments looks like O(n^2) is the best approach. If so wont it be simpler to check each subarray, of the given string, for palindrome.

for(int i=0; i<str.length(); i++)
  for(int j=i; j<str.length(); j++)
    if (isPalindrome(str.substring(i,j)) cout << str.substring(i,j)