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
- 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
- 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.
- If the sub-String satisfy the palindrome condition then print that string.
Program
[code lang=”java”]
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);
}
}
}
}
[/code]
Analysis
Worst case time complexity is O(n*n*n), here is n is the length of the string.
Space complexity is O(1)