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&lt;String&gt; 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&lt;String&gt; palindromeSet = new HashSet&lt;&gt;(list);
    String palindromeStr = null;
    for(int i = 0;i&lt;list.size();i++){
        palindromeStr = list.get(i);
        for(int j = i+1;j&lt;list.size();j++){
            palindromeStr = palindromeStr+list.get(j);
            if(isPalindrome(palindromeStr)){
                palindromeSet.add(palindromeStr);
            }
        }
    }
    return palindromeSet.size();
}

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

public static void main(String[] args) throws IOException{
    System.out.println(palindrome("arewenotdrawnonwardtonewera"));
}
}
/*
* Complete the function below.
*/


Do you still need it?

String[] strArray = str.split("");
List&lt;String&gt; 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&lt;list.size();i++){
    palindromeStr = list.get(i);


This should be

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


Note the spacing.

    for(int j = i+1;j&lt;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 -&gt; input
strArray -&gt; nothing, just inline it
palindromeSet -&gt; palindromes as it's clearly a set
palindromeStr -&gt; 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".