Counting the number of sub-strings that are palindrome

Question

I was solving a question on hackerearth.com today. https://www.hackerearth.com/problem/algorithm/subpalindrome-4/description/

Question:
For every string given as input, you need to tell us the number of subsequences of it that are palindromes (need not necessarily be distinct). Note that the empty string is not a palindrome.
Sample Input
1
aab
Sample Output
4
Explanation: The palindromic subsequences of "aab" are: "a", "a", "b", "aa", and the method returns 4.

I had to count the total number of sub-strings(not distinct) that are palindromes. I had to pass two test-cases out of which one was successful, and also the sample-input ran successfully. The second test-case failed with a 35.29% match.

Here is the code that I wrote in Java without using StringBuffer class:

import java.util.*;

class TestClass {
    int palin(String a)
    {
        int l=a.length();
        for(int i=0;i<l/2;i++)
        {
            if(a.charAt(i)!=a.charAt(l-1-i))
            return -1;
        }

        return 1;

    }
    public static void main(String args[] ) throws Exception {

        TestClass ob=new TestClass();

        Scanner in=new Scanner(System.in);
        int N = in.nextInt();
        in.nextLine(); /*I have included this because I have seen that when I
        input the string, the number is the value of N appears at its start*/
        for (int ii = 0; ii < N; ii++)
        {
            String aa=in.nextLine();
            String a=aa.toLowerCase();
            int l=a.length();
            int n=l;
            for(int i=0;i<l;i++)
            {
                for(int j=i+2;j<=l;j++)
                {
                    if(ob.palin(a.substring(i,j))>0)
                    n++;
                }
            }
            System.out.println(n);
        }
    } 

Did I go wrong somewhere logically? Or did I miss something?

Answer 1

A subsequence of a string is different from a substring. For example, consider the string "ABC":

Substrings: "", "A", "B", "C", "AB", "BC", "ABC"

Subsequences: All of the substrings, plus "AC"

More on subsequences: https://en.wikipedia.org/wiki/Subsequence