To find all palindrome sub-strings using java

Question

Given a string find all the sub-strings which are palindrome and print those strings.  A palindrome number is a number which is equal to its reverse. Even a single character is a palindrome.

Logic

• First, find all the sub-strings of the given string.
• Check each sub-string whether it is palindrome or not.
• If it is palindrome then print that string.

Algorithm

1. We use substring function in java to get the sub-string and store that in a separate string.  We have already covered how to find all the substrings
2. Get the length of the sub-string and create a loop to check whether the respective characters are equal. First and the last character must be equal. Second first and second last must be equal and so on.
3. If the sub-String satisfy the palindrome condition then print that string.

Program

class Substring
{
  public static void main(String ar[])
  {
       String str= "mamom";
       int len = str.length();
       int n,count=0;
       boolean flag= true;
     
       for(int i=0; i<len;i++)
       {
         for(int j=i+1;j<=len;j++)
        {
           /*To get substring from i to j-1*/
           String sub = str.substring(i,j);
           
           flag = true;                        //reset flag
           n = sub.length()-1;
           
           /*loop to check whether the substring is palindrome*/
           for(int k=0; k<sub.length()/2;k++,n--)
           {  
             /*In string 'madam' we check 
              * sub[0] == sub[4]
              * sub[1] == sub[3]
              * Both are true, so string is palindrome*/
             
             if(sub.charAt(k) == sub.charAt(n))   
               continue;
             else
             {
               /*Condition for palindrome failed*/
               flag =false;
               break;
             }
             
           }
           /*if the sub-string is palindrome(flag remains true)*/ 
           if(flag)
             System.out.println(sub);
                
         }

       }
  
  }
}

Analysis

Worst case time complexity is O(n*n*n), here is n is the length of the string.

Space complexity is O(1)