# Finding all possible distinct palindromes of a string

There was some online test where I was asked about finding all possible distinct palindromes of a string.

Here I had to give the count of all possible distinct palindromes of a given string (continuous substring). Here, a single character word is considered a palindrome.

Below is what I did. Can you please tell me if it is good OR there is a scope of improvement?

public class Solution {
/*
* Complete the function below.
*/

static int palindrome(String str) {
String[] strArray = str.split("");
List<String> list = Arrays.asList(strArray);
list = list.subList(1, list.size());
//Set does'nt allow duplicates.
//Sublist is required because split method gives an extra space.
Set<String> palindromeSet = new HashSet<>(list);
String palindromeStr = null;
for(int i = 0;i<list.size();i++){
palindromeStr = list.get(i);
for(int j = i+1;j<list.size();j++){
palindromeStr = palindromeStr+list.get(j);
if(isPalindrome(palindromeStr)){
}
}
}
return palindromeSet.size();
}

static boolean isPalindrome(String str){
char[] chars = str.toCharArray();
for(int i =0;i<(chars.length/2);i++){
if(chars[i] != chars[chars.length-1-i]){
return false;
}
}
return true;
}

public static void main(String[] args) throws IOException{
}
}


/*
* Complete the function below.
*/


Do you still need it?

String[] strArray = str.split("");
List<String> list = Arrays.asList(strArray);
list = list.subList(1, list.size());


That's ugly. You could work with the original String or use str.toCharArray() if you really needed an array. But you don't.

//Set does'nt allow duplicates.


True, but rather well-known. And a typo.

//Sublist is required because split method gives an extra space.


True, but misplaced by a few lines. Full line comments belong before the block they describe.

String palindromeStr = null;
for(int i = 0;i<list.size();i++){
palindromeStr = list.get(i);


This should be

for(int i = 0; i < list.size(); i++){
String palindromeStr = list.get(i);


Note the spacing.

    for(int j = i+1;j<list.size();j++){
palindromeStr = palindromeStr+list.get(j);


This is a pretty slow way of creating what

   String palindromeStr = str.substring(i, j);


could give you. By creating your string incrementally you gain nothing: Because of strings being immutable, their whole content gets copied on every step.

This way the complexity is O(n**3) and could be reduced(*) to O(n**2) by simply defining a method working on a substring like

 static boolean isPalindrome(String str, int start, int end) ...


You should improve both spacing (just press Ctrl-Shift-F in Eclipse) and naming, maybe as follows:

• str -> input
• strArray -> nothing, just inline it
• palindromeSet -> palindromes as it's clearly a set
• palindromeStr -> substring or candidate as it's not always a palindrome

Your naming is not really bad, but you concentrate on the type too much and I can imagine to get lost in a bunch of names like intListSetArray and strDoubleMap without any clue what's the variable good for.

I'd bet there's a faster algorithm, but I haven't figured it out yet.

(*) I'm assuming that isPalindrome is O(1) on the average, which is true for normal strings, but not for e.g. "aaaa....a".

• For a faster algorithm, I hypothesize the following: iterate to each character and find all palindromes with that character as the center character of a palindrome (expanding outwards until a palindrome is not possible). This works for odd length palindromes. For even length palindromes you pick the space in between characters as the "middle spot" and do the same thing. I think this is an $O(n^2)$ algorithm. – JS1 Jun 19 '15 at 2:12
• @JS1 Sure! You expand a palindrome by checking a single character pair, so you really get them all in quadratic time. +++ I guess, it could be done even faster as the degenerate cases like "aaaa....a" contain O(n**2) palindromes but only O(n) distinct ones. Maybe something like Rabin–Karp.... – maaartinus Jun 19 '15 at 2:35