class Solution {
    /**
    Approach used: Dynamic Programming (Longest Common Subsequence – LCS)
    The code computes the Longest Common Subsequence (LCS) between strings s and t using a DP table
    dp[i][j] stores the length of LCS of the first i characters of s and first j characters of t.
        If characters match (s[i-1] == t[j-1]), then dp[i][j] = 1 + dp[i-1][j-1]; 
        otherwise take the maximum of skipping one character from either string.
    After filling the table, the LCS length is dp[n][m].
    If LCS length equals the length of s, 
        then all characters of s appear in order in t, meaning s is a subsequence of t.
    */
    public boolean isSubsequence(String s, String t) {
        int n = s.length();
        int m = t.length();

        int length = findLCS(s, t, n, m);

        if(length == s.length())
            return true;

        return false;
    }

    public int findLCS(String s1, String s2, int n, int m)
    {
        // create a matrix
        int[][] t = new int[n+1][m+1];

        // initialise matrix with base condition
        for(int i=0; i<n+1; i++)
        {
            for(int j=0; j<m+1; j++)
            {
                if(i == 0 || j == 0)
                    t[i][j] = 0;
            }
        }

        // fill the matrix - LCS
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                if(s1.charAt(i-1) == s2.charAt(j-1))
                {
                    t[i][j] = 1 + t[i-1][j-1];
                }
                else
                    t[i][j] = Math.max( t[i-1][j], t[i][j-1] );
            }
        }
        return t[n][m];
    }
}