Dolly Sharma

Posted on Mar 22

Longest Common Substring

#algorithms #computerscience #cpp #coding

🔹 Definition

👉 Longest substring that is:

Present in both strings
Continuous (no skipping allowed) ❗

🔹 Difference from LCS

Feature	Subsequence	Substring
Continuous	❌	✅
DP reset	❌	✅ (important)

🔥 Core Idea

If characters match:

dp[i][j] = 1 + dp[i-1][j-1]

If NOT match:

dp[i][j] = 0   // 🔥 RESET (this is key difference)

🔹 Code (Correct & Clean C++)

int longestCommonSubstring(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    int ans = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1]){
                dp[i][j] = 1 + dp[i-1][j-1];
                ans = max(ans, dp[i][j]);
            }
            else{
                dp[i][j] = 0;  // 🔥 important
            }
        }
    }

    return ans;
}

🔹 Optimized Space (O(m)) 🚀

int longestCommonSubstring(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    vector<int> prev(m+1, 0), curr(m+1, 0);
    int ans = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1]){
                curr[j] = 1 + prev[j-1];
                ans = max(ans, curr[j]);
            }
            else{
                curr[j] = 0; // reset
            }
        }
        prev = curr;
    }

    return ans;
}

🔥 Print Longest Common Substring

👉 Trick:

Track ending index
Extract substring

🔹 Code (Print substring)

string printLCSubstring(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    int maxLen = 0;
    int endIndex = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1]){
                dp[i][j] = 1 + dp[i-1][j-1];

                if(dp[i][j] > maxLen){
                    maxLen = dp[i][j];
                    endIndex = i; // track end
                }
            }
        }
    }

    return s1.substr(endIndex - maxLen, maxLen);
}

🔹 Example

s1 = "abcde"
s2 = "abfce"

👉 Output:

"ab"

🧠 Key Intuition

Match → extend substring
Not match → break (reset to 0)

⚠️ Common Mistake

❌ Writing:

dp[i][j] = max(...)

👉 That is LCS (wrong problem)

🔥 Interview Tip

If interviewer says:

“Longest common substring”

👉 Immediately think:

“Reset DP to 0 when mismatch”

🚀 Summary

Substring = continuous → reset DP
Use diagonal only
Track max length

If you want next level:
✅ Difference table (LCS vs substring vs subsequence problems)
✅ Hard problems based on this
✅ Visual DP table like your image

Just tell me 👍

Forem