Find all substrings that are palindromes

Question

If the input is 'abba' then the possible palindromes are a, b, b, a, bb, abba.
I understand that determining if string is palindrome is easy. It would be like:

public static boolean isPalindrome(String str) {
 int len = str.length();
 for(int i=0; i<len/2; i++) {
     if(str.charAt(i)!=str.charAt(len-i-1) {
         return false;
     }
 return true;  
}

But what is the efficient way of finding palindrome substrings?

Answer 1

I just came up with my own logic which helps to solve this problem. Happy coding.. :-)

System.out.println("Finding all palindromes in a given string : ");
        subPal("abcacbbbca");

private static void subPal(String str) {
        String s1 = "";
        int N = str.length(), count = 0;
        Set<String> palindromeArray = new HashSet<String>();
        System.out.println("Given string : " + str);
        System.out.println("******** Ignoring single character as substring palindrome");
        for (int i = 2; i <= N; i++) {
            for (int j = 0; j <= N; j++) {
                int k = i + j - 1;
                if (k >= N)
                    continue;
                s1 = str.substring(j, i + j);
                if (s1.equals(new StringBuilder(s1).reverse().toString())) {
                    palindromeArray.add(s1);
                }
            }

        }
        System.out.println(palindromeArray);
        for (String s : palindromeArray)
            System.out.println(s + " - is a palindrome string.");
        System.out.println("The no.of substring that are palindrome : "
                + palindromeArray.size());
    }

Output:-
Finding all palindromes in a given string : 
Given string : abcacbbbca
******** Ignoring single character as substring palindrome ********
[cac, acbbbca, cbbbc, bb, bcacb, bbb]
cac - is a palindrome string.
acbbbca - is a palindrome string.
cbbbc - is a palindrome string.
bb - is a palindrome string.
bcacb - is a palindrome string.
bbb - is a palindrome string.
The no.of substring that are palindrome : 6

Answer 2

I tried the following code and its working well for the cases Also it handles individual characters too

Few of the cases which passed:

abaaa --> [aba, aaa, b, a, aa] 
geek  --> [g, e, ee, k] 
abbaca --> [b, c, a, abba, bb, aca] 
abaaba -->[aba, b, abaaba, a, baab, aa] 
abababa -->[aba, babab, b, a, ababa, abababa, bab] 
forgeeksskeegfor --> [f, g, e, ee, s, r, eksske, geeksskeeg, 
                      o, eeksskee, ss, k, kssk]

Code

static Set<String> set = new HashSet<String>(); 
static String DIV = "|";

public static void main(String[] args) {
    String str = "abababa";
    String ext = getExtendedString(str);

    // will check for even length palindromes
    for(int i=2; i<ext.length()-1; i+=2) {
        addPalindromes(i, 1, ext);
    }
    // will check for odd length palindromes including individual characters
    for(int i=1; i<=ext.length()-2; i+=2) {
        addPalindromes(i, 0, ext);
    }
    System.out.println(set);
}

/*
 * Generates extended string, with dividors applied
 * eg: input = abca
 * output = |a|b|c|a|
 */
static String getExtendedString(String str) {
    StringBuilder builder = new StringBuilder();
    builder.append(DIV);
    for(int i=0; i< str.length(); i++) {
        builder.append(str.charAt(i));
        builder.append(DIV);

    }
    String ext = builder.toString();
    return ext;
}

/*
 * Recursive matcher
 * If match is found for palindrome ie char[mid-offset] = char[mid+ offset]
 * Calculate further with offset+=2
 * 
 * 
 */
static void addPalindromes(int mid, int offset, String ext) {
    // boundary checks
    if(mid - offset <0 || mid + offset > ext.length()-1) {
        return;
    }
    if (ext.charAt(mid-offset) == ext.charAt(mid+offset)) {
        set.add(ext.substring(mid-offset, mid+offset+1).replace(DIV, ""));
        addPalindromes(mid, offset+2, ext);
    }
}

Hope its fine

Answer 3

So, each distinct letter is already a palindrome - so you already have N + 1 palindromes, where N is the number of distinct letters (plus empty string). You can do that in single run - O(N).

Now, for non-trivial palindromes, you can test each point of your string to be a center of potential palindrome - grow in both directions - something that Valentin Ruano suggested.
This solution will take O(N^2) since each test is O(N) and number of possible "centers" is also O(N) - the center is either a letter or space between two letters, again as in Valentin's solution.

Note, there is also O(N) solution to your problem, based on Manacher's algoritm (article describes "longest palindrome", but algorithm could be used to count all of them)

Answer 4

    // Maintain an Set of palindromes so that we get distinct elements at the end
    // Add each char to set. Also treat that char as middle point and traverse through string to check equality of left and right char


static int palindrome(String str) {

    Set<String> distinctPln = new HashSet<String>();
    for (int i=0; i<str.length();i++) {
        distinctPln.add(String.valueOf(str.charAt(i)));
        for (int j=i-1, k=i+1; j>=0 && k<str.length(); j--, k++) {
            // String of lenght 2 as palindrome
            if ( (new Character(str.charAt(i))).equals(new Character(str.charAt(j)))) { 
                distinctPln.add(str.substring(j,i+1));
            }
            // String of lenght 2 as palindrome
            if ( (new Character(str.charAt(i))).equals(new Character(str.charAt(k)))) { 
                distinctPln.add(str.substring(i,k+1));
            }
            if ( (new Character(str.charAt(j))).equals(new Character(str.charAt(k)))) { 
                distinctPln.add(str.substring(j,k+1));
            } else {
                continue;
            }
        }
    }

    Iterator<String> distinctPlnItr = distinctPln.iterator();
    while ( distinctPlnItr.hasNext()) {
        System.out.print(distinctPlnItr.next()+ ",");
    }
    return distinctPln.size();

}

Answer 5

This can be done in O(n), using Manacher's algorithm.

The main idea is a combination of dynamic programming and (as others have said already) computing maximum length of palindrome with center in a given letter.

---

What we really want to calculate is radius of the longest palindrome, not the length. The radius is simply length/2 or (length - 1)/2 (for odd-length palindromes).

After computing palindrome radius pr at given position i we use already computed radiuses to find palindromes in range [i - pr ; i]. This lets us (because palindromes are, well, palindromes) skip further computation of radiuses for range [i ; i + pr].

While we search in range [i - pr ; i], there are four basic cases for each position i - k (where k is in 1,2,... pr):

• no palindrome (radius = 0) at i - k
  (this means radius = 0 at i + k, too)
• inner palindrome, which means it fits in range
  (this means radius at i + k is the same as at i - k)
• outer palindrome, which means it doesn't fit in range
  (this means radius at i + k is cut down to fit in range, i.e because i + k + radius > i + pr we reduce radius to pr - k)
• sticky palindrome, which means i + k + radius = i + pr
  (in that case we need to search for potentially bigger radius at i + k)

Full, detailed explanation would be rather long. What about some code samples? :)

I've found C++ implementation of this algorithm by Polish teacher, mgr Jerzy Wałaszek.
I've translated comments to english, added some other comments and simplified it a bit to be easier to catch the main part.
Take a look here.

---

Note: in case of problems understanding why this is O(n), try to look this way:
after finding radius (let's call it r) at some position, we need to iterate over r elements back, but as a result we can skip computation for r elements forward. Therefore, total number of iterated elements stays the same.

Answer 6

public class PolindromeMyLogic {

static int polindromeCount = 0;

private static HashMap<Character, List<Integer>> findCharAndOccurance(
        char[] charArray) {
    HashMap<Character, List<Integer>> map = new HashMap<Character, List<Integer>>();
    for (int i = 0; i < charArray.length; i++) {
        char c = charArray[i];
        if (map.containsKey(c)) {
            List list = map.get(c);
            list.add(i);
        } else {
            List list = new ArrayList<Integer>();
            list.add(i);
            map.put(c, list);
        }
    }
    return map;
}

private static void countPolindromeByPositions(char[] charArray,
        HashMap<Character, List<Integer>> map) {
    map.forEach((character, list) -> {
        int n = list.size();
        if (n > 1) {
            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (list.get(i) + 1 == list.get(j)
                            || list.get(i) + 2 == list.get(j)) {
                        polindromeCount++;
                    } else {
                        char[] temp = new char[(list.get(j) - list.get(i))
                                + 1];
                        int jj = 0;
                        for (int ii = list.get(i); ii <= list
                                .get(j); ii++) {
                            temp[jj] = charArray[ii];
                            jj++;
                        }
                        if (isPolindrome(temp))
                            polindromeCount++;
                    }

                }
            }
        }
    });
}

private static boolean isPolindrome(char[] charArray) {
    int n = charArray.length;
    char[] temp = new char[n];
    int j = 0;
    for (int i = (n - 1); i >= 0; i--) {
        temp[j] = charArray[i];
        j++;
    }
    if (Arrays.equals(charArray, temp))
        return true;
    else
        return false;
}

public static void main(String[] args) {
    String str = "MADAM";
    char[] charArray = str.toCharArray();
    countPolindromeByPositions(charArray, findCharAndOccurance(charArray));
    System.out.println(polindromeCount);
}
}

Try out this. Its my own solution.