# Thread: How to count number of palindrome in a string??

1. Member
Join Date
Aug 2008
Posts
13
Rep Power
0

## How to count number of palindrome in a string??

Hai all i have a problem in palindrome. this is the question:
Create a function findPalin() that takes a string of characters as an argument and returns the number of palindromes (a string in which the sequence of characters is the same forwards and backwards) in that string. There is no special character. This function should be as fast as possible.

Ex:

"aa" returns 1
"aabb" returns 2
"222" returns 3
"baaab3" returns 4

How is the algorithm to solve this problem?. anyone can helo me, please?.

2. Originally Posted by i4ba1
Hai all i have a problem in palindrome. this is the question:
Create a function findPalin() that takes a string of characters as an argument and returns the number of palindromes (a string in which the sequence of characters is the same forwards and backwards) in that string. There is no special character. This function should be as fast as possible.

Ex:

"aa" returns 1
"aabb" returns 2
"222" returns 3
"baaab3" returns 4

How is the algorithm to solve this problem?. anyone can helo me, please?.
Do you want to count 'sub palindromes' as palindromes as well? i.e. "abbaabba" contains how many palindromes? If so you have to check every substring starting at position i and ending at position j (exclusive) and see if it is a palindrome or not. The loop looks like this:

Java Code:
```for (int i= 0; i < string.length()-2; i++)
for (int j= i+2; i < string.length(); j++)
// check substring at position [i, j)```
The is a O(n^2) algorithm and I doubt if it can be done any better ...

kind regards,

Jos

3. Member
Join Date
Aug 2008
Posts
13
Rep Power
0
This is my code for palindrome:
Java Code:
```private int countPalin(String str)
{
int numPalin = 0;
for (int i = 2; i <= str.length(); i++)
{
for (int j = 0; j+i <= str.length(); j++)
{
System.out.println("j "+j);
System.out.println("i "+i);
String test = str.substring(j, i);

if (checkPalin(test) && !test.equals(""))
{
System.out.println("test "+test);
numPalin++;
}
}
}

return numPalin;
}

private boolean checkPalin(String str)
{
StringBuffer sb = new StringBuffer(str);
String rev = sb.reverse().toString();

//System.out.println("str "+str);
//System.out.println("rev "+rev);
if (!str.equalsIgnoreCase(rev))
{
return false;
}

return true;
}```
this code run for word "aa","aabb","222" but with word "baaab3" the error String index out of bounds sho. any one can help me to solve this problem?.

4. Originally Posted by i4ba1
This is my code for palindrome:
Java Code:
```private int countPalin(String str)
{
int numPalin = 0;
for (int i = 2; i <= str.length(); i++)
{
for (int j = 0; j+i <= str.length(); j++)
{
System.out.println("j "+j);
System.out.println("i "+i);
String test = str.substring(j, i);

if (checkPalin(test) && !test.equals(""))
{
System.out.println("test "+test);
numPalin++;
}
}
}

return numPalin;
}

private boolean checkPalin(String str)
{
StringBuffer sb = new StringBuffer(str);
String rev = sb.reverse().toString();

//System.out.println("str "+str);
//System.out.println("rev "+rev);
if (!str.equalsIgnoreCase(rev))
{
return false;
}

return true;
}```
this code run for word "aa","aabb","222" but with word "baaab3" the error String index out of bounds sho. any one can help me to solve this problem?.
Your first two loop bounds are incorrect; they should be:

Java Code:
```for (int i= 0; i < s.length()-2; i++)
for (int j= i+2; j <= s.length(); j++)
...```
These loops iterate over all pairs (i, j), i < j <= s.length() where s.substring(i, j) has to be checked for the palindrome property. Note that i+2 <= j which takes care that no trivial palindromes are checked.

kind regards,

Jos

5. Member
Join Date
Aug 2008
Posts
13
Rep Power
0
Thank you JosAh it's working. i try your loop, but why the first loop must str.length() -2?, if i try without str.length() -2 it's working to.

6. Originally Posted by i4ba1
Thank you JosAh it's working. i try your loop, but why the first loop must str.length() -2?, if i try without str.length() -2 it's working to.
You only want to test possible palindromes with a length of at least 2; smaller palindromes, e.g. "a" are trivial and you don't want to count them.

kind regards,

Jos

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•