Longest Common Substring | Solved using Tabulation

Given two strings text1 and text2, find the length of the longest common substring between them. A substring is a contiguous block of characters. Unlike subsequence, characters must be adjacent and in the same order in both strings.

Here’s the [Problem Link] to begin with.

Example 1

text1 = "abcjklp"
text2 = "acjkp"
Output: 3
Explanation: One longest common substring is "cjk" with length 3.

Example 2

text1 = "zxabcdezy"
text2 = "yzabcdezx"
Output: 6
Explanation: "abcdez" is a common substring of length 6.

Goal: return only the length of the longest common substring.

Tabulation

Intuition and Approach

This is a classic dynamic programming problem. Let dp[i][j] be the length of the longest common suffix of the prefixes text1[:i] and text2[:j].
Transition:

• If text1[i-1] == text2[j-1], then the common suffix extends by 1, so dp[i][j] = 1 + dp[i-1][j-1].
• Otherwise the common suffix breaks, so dp[i][j] = 0.

Track the maximum over all dp[i][j] while filling the table. Initialize the first row and column to 0 because an empty prefix has no common substring.

Code Implementation

class Solution:
    def longestCommonSubstr(self, text1, text2):
        n = len(text1)
        m = len(text2)
        maxi = 0
        dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]
        for ind2 in range(0, m + 1):
            dp[0][ind2] = 0
        for ind1 in range(0, n + 1):
            dp[ind1][0] = 0
        for ind1 in range(1, n + 1):
            for ind2 in range(1, m + 1):
                if text1[ind1 - 1] == text2[ind2 - 1]:
                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
                    maxi = max(maxi, dp[ind1][ind2])
                else:
                    dp[ind1][ind2] = 0
        return maxi

Code explanation

• dp is a 2D table of size (n+1) x (m+1) where borders are 0.
• When characters match, extend the previous diagonal value by 1 to continue the current matching substring.
• When characters differ, reset to 0 because substrings must be contiguous.
• maxi stores the best length seen so far.

Time and Space Complexity

• Precise: filling n*m cells with O(1) work each gives O(n*m) time. The table uses O(n*m) space.
• Simplified: O(n*m) time and O(n*m) space.

Conclusion

Bottom up DP with a full table is straightforward and helps visualize contiguous matches through the diagonal extension rule.

Tabulation (Space Optimize)

Intuition and Approach

dp[i][j] depends only on dp[i-1][j-1]. This allows reducing space to two 1D arrays representing the previous row and the current row.

Code Implementation

class Solution:
    def longestCommonSubstr(self, text1, text2):
        n = len(text1)
        m = len(text2)
        maxi = 0
        prev = [0 for _ in range(m + 1)]
        for ind1 in range(1, n + 1):
            curr = [0 for _ in range(m + 1)]
            for ind2 in range(1, m + 1):
                if text1[ind1 - 1] == text2[ind2 - 1]:
                    curr[ind2] = 1 + prev[ind2 - 1]
                    maxi = max(maxi, curr[ind2])
                else:
                    curr[ind2] = 0
            prev = curr
        return maxi

Code explanation

• prev[j] stores values for row ind1 - 1, and curr[j] for row ind1.
• On match, take 1 + prev[ind2 - 1] to continue the substring.
• On mismatch, reset curr[ind2] to 0 since contiguity is broken.
• Track the maximum along the way, then return it.

Time and Space Complexity

• Precise: still processes n*m cells, so O(n*m) time. Uses two arrays of length m+1, so O(m) extra space.
• Simplified: O(n*m) time and O(min(n, m)) space if you iterate along the shorter string as columns.

Conclusion

Space optimization preserves the same transitions and runtime while cutting memory to linear in one dimension. Use this when inputs are large and only the length is required.

Final takeaway

• Longest common substring requires contiguity, so mismatches reset the DP cell to 0.
• Tabulation gives a clear and reliable O(n*m) solution.
• Space optimized tabulation reduces memory to O(min(n, m)) while keeping the time optimal.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.