Finding all possible distinct palindromes of a string

Question

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)){
                palindromeSet.add(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{
    System.out.println(palindrome("arewenotdrawnonwardtonewera"));
}
}

Answer 1

/*
* 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".