Palindrome Count  : All possible substring palindromes inside a string

A string is said to be palindrome, if the reverse of the string is same as itself.
A sub string is any continuous sequence of characters in the string.

Given a string S, finding all non empty sub strings that are palindromes.

For Example:

For Input string , S =abcba

Output should be all possible substring palindromes :

Palindrome 1 : a
Palindrome 2 : abcba
Palindrome 3 : b
Palindrome 4: bcb
Palindrome 5 : c
Palindrome 6 : b
Palindrome 7 : a



Algorithm:

1.  Input : a string str.
2.  for i from 0 to str.length-1  do
3.  for j from i+1 to str.length  do
4.  result = str.substring(i,j)
5. check if result is palindrome  then
6. increment counter


Complexity:  O(n3)


Java implementation of the algorithm:


import java.util.Scanner;

public class PalindromeCount {


    public static void main(String[] args) {
   
        System.out.println("Enter the string : ");
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        long startTime = System.currentTimeMillis();   
        int count = substr(str);
        System.out.println("Number of palindromes = "+count);
            long stopTime = System.currentTimeMillis();
            long elapsedTime = stopTime - startTime;
            System.out.println("Time Taken= "+(double)elapsedTime/1000+" sec");
    }
   
   

    private static int substr(String str) {
        int len = str.length();
        int count = 0;
        String result = "";
        for(int i = 0;i<len;i++){
            for(int j = i+1;j<=len;j++){
            result = str.substring(i,j);
            if(isPalindrome(result)){
                count = count + 1;
                System.out.println("Palindrome("+i+","+j+") "+(count)+" : "+result);
               
            }
            }
        }
        return count;
    }



    static boolean isPalindrome(String str){
        int len = str.length();
        boolean flag = false;
        String reverse = "";
        for(int i=len-1;i>=0;i--){
            reverse = reverse+str.charAt(i);
        }
        if(str.equals(reverse))
        flag = true;
        return flag;
    }
}


Output:

Enter the string : abcba
Palindrome(0,1) 1 : a
Palindrome(0,5) 2 : abcba
Palindrome(1,2) 3 : b
Palindrome(1,4) 4 : bcb
Palindrome(2,3) 5 : c
Palindrome(3,4) 6 : b
Palindrome(4,5) 7 : a
Number of palindromes = 7
Time Taken= 0.002 sec