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?.

Quote:

---

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:

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

This is my code for palindrome:

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?.

Quote:

---

Originally Posted by i4ba1

This is my code for palindrome:

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:

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

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.

Quote:

---

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