CODEWITHSUNDEEP
algorithmperformancedynamic-programming
yobro97
yobro97

Reputation: 1145

Number of ways selecting a pair of non-overlapping substrings which are palindromes

Given a string s, it is expected to find the number of ways of selecting a pair of non-overlapping substrings which are palindromes.
For example in the string abcdcefdfdio, one way is selecting cdc and dfd.
My approach was a dp one: 

    String s = sc.next();
    int n = s.length();
    int firstsum[] = new int[n];//firstsum[i] stores the number of palindromes in the substring (0...i)
    int[][] A = new int[n][n];//A[i][j]=1 denotes the substring (i...j) is a palindrome and =0 otherwise
    for(int i=0;i<n;++i)
    {
        firstsum[i]=0;
        for(int j=i;j<n;++j)
        {
            if(check(s.substring(i,j+1))==1)
            {
                A[i][j]=1;
            }
            else
                A[i][j]=0;
        }
    }
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<=i;++j)
        {
            if(A[j][i]==1)
                firstsum[i]++;
        }
        if(i>0)
            firstsum[i]+=firstsum[i-1];
    }
    int cnt=0;
    for(int i=1;i<n;++i)
    {
        for(int j=i;j<n;++j)
            cnt+=A[i][j]*firstsum[i-1];
    }
    System.out.print(cnt);//answer

The solution is working but is exceeding the time limit. Is there a better approach, in DP preferably?

Upvotes: 0

Views: 786

Answers (1)

v78
v78

Reputation: 2933

Remove A[i][j] filling loop. Its O(n^3) in the worst case.

Try this code.

String s = sc.next();
int n = s.length();
int firstsum[] = new int[n];//firstsum[i] stores the number of palindromes in the substring (0...i)
int[][] A = new int[n][n];//A[i][j]=1 denotes the substring (i...j) is a palindrome and =0 otherwise

for(int i=0;i<n;++i)
{
     A[i][i]=1;
}

for(int len=1;len<n;++len)
{
    for(int i=0;i<n-len;++i)
    {
        if( s.charAt(i)==s.charAt(i+len) && (i+1>=i+len-1 || A[i+1][i+len-1]==1) )
        {
            A[i][len]=1;
        }
        else{
            A[i][len]=0;
        }
    }
}


for(int i=0;i<n;++i)
{
    firstsum[i]=0;
    for(int j=0;j<=i;++j)
    {
        if(A[j][i]==1)
            firstsum[i]++;
    }
    if(i>0)
        firstsum[i]+=firstsum[i-1];
}
int cnt=0;
for(int i=1;i<n;++i)
{
    for(int j=i;j<n;++j)
        cnt+=A[i][j]*firstsum[i-1];
}
System.out.print(cnt);//answer

Upvotes: 1

Related Questions