Longest Common Substring in DSA C - Time & Space Complexity

Time Complexity: Longest Common Substring

O(m * n)

Understanding Time Complexity

We want to understand how the time needed to find the longest common substring grows as the input strings get longer.

Specifically, how does the work change when the strings increase in size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int longestCommonSubstring(char *s1, char *s2) {
    int m = strlen(s1);
    int n = strlen(s2);
    int maxLen = 0;
    int dp[m+1][n+1];

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) dp[i][j] = 0;
            else if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if (dp[i][j] > maxLen) maxLen = dp[i][j];
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return maxLen;
}
    

This code finds the length of the longest substring common to both input strings using a 2D table.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over both strings filling the dp table.
• How many times: The inner code runs (m+1) * (n+1) times, where m and n are string lengths.

How Execution Grows With Input

As the strings get longer, the number of operations grows roughly by multiplying their lengths.

Input Size (m and n)	Approx. Operations
10	~100
100	~10,000
1000	~1,000,000

Pattern observation: Doubling the length roughly quadruples the work, showing a multiplication effect.

Final Time Complexity

Time Complexity: O(m * n)

This means the time needed grows proportionally to the product of the two string lengths.

Common Mistake

[X] Wrong: "The algorithm only depends on the length of one string, so it is O(n)."

[OK] Correct: The algorithm compares every character of one string with every character of the other, so both lengths matter and multiply the work.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming solves problems efficiently by breaking them into smaller parts.

Self-Check

"What if we only compared substrings starting at the same index in both strings? How would the time complexity change?"