8
\$\begingroup\$

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"));
}
}
\$\endgroup\$
4
\$\begingroup\$
/*
* 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".

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – JS1 Jun 19 '15 at 2:12
  • \$\begingroup\$ @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.... \$\endgroup\$ – maaartinus Jun 19 '15 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.