1. class Solution {
  2.     /**
  3.     Approach used: Dynamic Programming (Longest Common Subsequence – LCS)
  4.     The code computes the Longest Common Subsequence (LCS) between strings s and t using a DP table
  5.     dp[i][j] stores the length of LCS of the first i characters of s and first j characters of t.
  6.         If characters match (s[i-1] == t[j-1]), then dp[i][j] = 1 + dp[i-1][j-1]; 
  7.         otherwise take the maximum of skipping one character from either string.
  8.     After filling the table, the LCS length is dp[n][m].
  9.     If LCS length equals the length of s, 
  10.         then all characters of s appear in order in t, meaning s is a subsequence of t.
  11.     */
  12.     public boolean isSubsequence(String s, String t) {
  13.         int n = s.length();
  14.         int m = t.length();
  15.  
  16.         int length = findLCS(s, t, n, m);
  17.  
  18.         if(length == s.length())
  19.             return true;
  20.  
  21.         return false;
  22.     }
  23.  
  24.     public int findLCS(String s1, String s2, int n, int m)
  25.     {
  26.         // create a matrix
  27.         int[][] t = new int[n+1][m+1];
  28.  
  29.         // initialise matrix with base condition
  30.         for(int i=0; i<n+1; i++)
  31.         {
  32.             for(int j=0; j<m+1; j++)
  33.             {
  34.                 if(i == 0 || j == 0)
  35.                     t[i][j] = 0;
  36.             }
  37.         }
  38.  
  39.         // fill the matrix - LCS
  40.         for(int i=1; i<n+1; i++)
  41.         {
  42.             for(int j=1; j<m+1; j++)
  43.             {
  44.                 if(s1.charAt(i-1) == s2.charAt(j-1))
  45.                 {
  46.                     t[i][j] = 1 + t[i-1][j-1];
  47.                 }
  48.                 else
  49.                     t[i][j] = Math.max( t[i-1][j], t[i][j-1] );
  50.             }
  51.         }
  52.         return t[n][m];
  53.     }
  54. }