class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        /* Q28 dp playlist , every cell denotes LCS for that coloumn string
        with that row string 

        2)smallest problem on bottom left , biggest problem on 0,0
        
        3)making 2d dp array , keeping text 1 on coloumn and text2 on row +1
        for dash or empty string

        */

        int m = text1.length() , n = text2.length();
        int[][] dp = new int[m+1][n+1];

        //last coloumn , last row will be 0 for dashes
        // i represent text1 , j represent text2
        for(int i = m-1 ; i>= 0 ; i--){

            for(int j = n-1 ; j>=0 ; j--){
                
                //if first chars are equal , diagonally right +1 will be ans
                if(text1.charAt(i) == text2.charAt(j))
                dp[i][j] = dp[i+1][j+1] + 1;

                //else max (horizontal ,vertical) will be answer
                else
                dp[i][j] = Math.max(dp[i+1][j] , dp[i][j+1]);
            }
        }

        return dp[0][0];
    }
}