Longest Common Substring

Problem Statement: Longest Common Substring

A substring of a string is a subsequence in which all the characters are consecutive. Given two strings, we need to find the longest common substring.

We need to print the length of the longest common substring.

Approach - Bottom Up 2D

• Since this is substring so if character don’t match then we just have to reset this

public class Solution {
    public static int lcs(String str1, String str2){
        // Write your code here.
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        int ans = 0;
        for (int i = str1.length() - 1; i >= 0 ; i--) {
            for (int j = str2.length() - 1; j >= 0; j--) {
                if (str1.charAt(i) == str2.charAt(j)) {
                    int val = 1 + dp[i+1][j+1];
                    dp[i][j] = Math.max(dp[i][j], val);
                    ans = Math.max(ans, val);
                } else {
                    dp[i][j] = 0;
                }
            }
        }
 
        return ans;
    }
}