RepeatingSub-Sequence.cpp

/*
Given a string, find if there is any sub-sequence that repeats itself.
A sub-sequence of a string is defined as a sequence of characters generated by deleting some characters in the string without changing the order of the remaining characters.

Input:
string

Output:

0/1
0 -> No
1 -> Yes 
Example:

abab ------> yes, ab is repeated. So, return 1. 
abba ------> No, a and b follow different order. So, return 0. 
NOTE : sub-sequence length should be greater than or equal to 2

LINK: https://www.interviewbit.com/problems/repeating-subsequence/
*/

int Solution::anytwo(string A)
{
    int n = A.length();
    int dp[n+1][n+1];
    memset(dp,0,sizeof(dp));
 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(A[i-1]==A[j-1] && i!=j)
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if(dp[i][j]>1)
                return 1;
        }
    }
    return 0;
}