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

• JS1: 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.
• maaartinus: @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....