Longest Common Substring

🎯

Longest Common Substring

mediumDPAmazonGoogle

Imagine two DNA sequences from different species. Finding the longest common substring helps identify the longest matching genetic segment, which can be crucial for evolutionary studies.

💡 This problem asks for the longest contiguous matching segment between two strings. Beginners often confuse it with longest common subsequence, which allows gaps. The contiguous requirement makes it trickier and requires different techniques.

📋

Problem Statement

Given two strings s1 and s2, find the length of the longest substring that appears in both strings. A substring is a contiguous sequence of characters within a string. Return the length of this longest common substring.

1 ≤ length of s1, s2 ≤ 10^5Strings consist of lowercase English letters only

💡

Example

Input"s1 = 'abcde', s2 = 'abfce'"

Output2

The longest common substring is 'ab' which appears in both strings.

Input"s1 = 'zxabcdezy', s2 = 'yzabcdezx'"

Output6

The longest common substring is 'abcdez' which has length 6.

• One or both strings empty → output 0
• No common characters at all → output 0
• Strings are identical → output length of either string
• Common substring at the very end or start of strings → ensure boundary handling

🔁

Why DP?

Why greedy fails:

A greedy approach might try to match characters from the start and extend as long as possible, but it fails when the longest common substring is in the middle. For example, s1='abcxyz', s2='xyzabc' greedy from start finds 'abc' or 'xyz' but misses longer matches in other positions.

DP state:

dp[i][j] = length of the longest common substring ending exactly at s1[i-1] and s2[j-1].

Recurrence:dp[i][j] = dp[i-1][j-1] + 1 if s1[i-1] == s2[j-1] else 0

If characters match, extend the previous substring by 1; otherwise, reset to 0 because substring must be contiguous.

⚠️

Common Mistakes

Confusing longest common substring with longest common subsequence

Incorrect results because subsequence allows gaps, substring requires contiguity

✅ Use DP that resets length to zero when characters don't match

Not resetting dp[i][j] to zero when characters differ

Incorrectly accumulates lengths leading to wrong answers

✅ Explicitly set dp[i][j] = 0 if characters don't match

Iterating dp array forward in space optimized approach

Overwrites dp[j-1] before using it, causing wrong results

✅ Iterate backwards over j to preserve previous dp[j-1]

Using substring search inside nested loops in brute force

Leads to very high time complexity and TLE

✅ Avoid brute force for large inputs; use DP instead

🧠

Brute Force (Nested Loops Checking All Substrings)

💡 This approach tries every possible substring of s1 and checks if it appears in s2. It is simple to understand but inefficient, serving as a baseline to appreciate DP optimizations.

Intuition

Check all substrings of s1 and for each, check if it exists in s2. Keep track of the longest such substring.

Algorithm

1. Generate all substrings of s1 using two nested loops.
2. For each substring, check if it exists in s2 using a substring search.
3. Keep track of the maximum length of substrings found in both strings.
4. Return the maximum length found.

💡 The nested loops and substring search make it hard to see the inefficiency at first, but it clearly covers all possibilities.

Recurrence:N/A

</>

Code

def longest_common_substring_brute(s1, s2):
    max_len = 0
    n, m = len(s1), len(s2)
    for i in range(n):
        for j in range(i + 1, n + 1):
            sub = s1[i:j]
            if sub in s2:
                max_len = max(max_len, j - i)
    return max_len

# Driver code
if __name__ == '__main__':
    print(longest_common_substring_brute('abcde', 'abfce'))  # Output: 2

Line Notes

for i in range(n):Outer loop picks start index of substring in s1

for j in range(i + 1, n + 1):Inner loop picks end index (exclusive) of substring

sub = s1[i:j]Extract current substring from s1

if sub in s2:Check if substring exists anywhere in s2

public class LongestCommonSubstringBrute {
    public static int longestCommonSubstring(String s1, String s2) {
        int maxLen = 0;
        int n = s1.length(), m = s2.length();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                String sub = s1.substring(i, j);
                if (s2.contains(sub)) {
                    maxLen = Math.max(maxLen, j - i);
                }
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubstring("abcde", "abfce")); // Output: 2
    }
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop selects start index in s1

for (int j = i + 1; j <= n; j++) {Inner loop selects end index (exclusive)

String sub = s1.substring(i, j);Extract substring from s1

if (s2.contains(sub)) {Check if s2 contains this substring

#include <iostream>
#include <string>
using namespace std;

int longestCommonSubstringBrute(const string& s1, const string& s2) {
    int maxLen = 0;
    int n = s1.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            string sub = s1.substr(i, j - i);
            if (s2.find(sub) != string::npos) {
                maxLen = max(maxLen, j - i);
            }
        }
    }
    return maxLen;
}

int main() {
    cout << longestCommonSubstringBrute("abcde", "abfce") << endl; // Output: 2
    return 0;
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop picks start index in s1

for (int j = i + 1; j <= n; j++) {Inner loop picks end index (exclusive)

string sub = s1.substr(i, j - i);Extract substring from s1

if (s2.find(sub) != string::npos) {Check if s2 contains substring

function longestCommonSubstringBrute(s1, s2) {
    let maxLen = 0;
    const n = s1.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j <= n; j++) {
            const sub = s1.substring(i, j);
            if (s2.includes(sub)) {
                maxLen = Math.max(maxLen, j - i);
            }
        }
    }
    return maxLen;
}

// Test
console.log(longestCommonSubstringBrute('abcde', 'abfce')); // Output: 2

Line Notes

for (let i = 0; i < n; i++) {Outer loop selects start index in s1

for (let j = i + 1; j <= n; j++) {Inner loop selects end index (exclusive)

const sub = s1.substring(i, j);Extract substring from s1

if (s2.includes(sub)) {Check if s2 contains substring

⏱

Complexity

TimeO(n^3) in worst case due to substring extraction and search

SpaceO(1) additional space

Two nested loops generate O(n^2) substrings, each substring search in s2 is O(n), total O(n^3).

💡 For n=20, this means 20^3=8000 operations, which is slow but still manageable; for n=1000, it becomes 1 billion operations, too slow.

Interview Verdict: TLE / Use only to introduce problem

This approach is too slow for large inputs but helps understand the problem and motivates DP.

🧠

Top-Down DP with Memoization

💡 This approach uses recursion with memoization to avoid recomputing overlapping subproblems, improving efficiency over brute force but still not optimal for very large inputs.

Intuition

Define a recursive function that returns the length of the longest common substring ending at indices i and j. Use memoization to store results and avoid recomputation.

Algorithm

1. Define a recursive function lcs(i, j) that returns longest common substring length ending at s1[i-1], s2[j-1].
2. If characters match, return 1 + lcs(i-1, j-1), else 0.
3. Use a memo dictionary to store computed results for (i, j).
4. Iterate over all i, j pairs to find the maximum value returned by lcs.

💡 The recursion with memoization is tricky because it only counts substrings ending at specific indices, so we must check all pairs.

Recurrence:dp(i,j) = dp(i-1,j-1) + 1 if s1[i-1] == s2[j-1] else 0

</>

Code

def longest_common_substring_memo(s1, s2):
    n, m = len(s1), len(s2)
    memo = {}
    max_len = 0

    def lcs(i, j):
        if i == 0 or j == 0:
            return 0
        if (i, j) in memo:
            return memo[(i, j)]
        if s1[i-1] == s2[j-1]:
            memo[(i, j)] = 1 + lcs(i-1, j-1)
        else:
            memo[(i, j)] = 0
        return memo[(i, j)]

    for i in range(1, n+1):
        for j in range(1, m+1):
            length = lcs(i, j)
            if length > max_len:
                max_len = length
    return max_len

# Driver code
if __name__ == '__main__':
    print(longest_common_substring_memo('abcde', 'abfce'))  # Output: 2

Line Notes

memo = {}Cache to store results of subproblems to avoid recomputation

def lcs(i, j):Recursive function to compute longest substring ending at i-1, j-1

if s1[i-1] == s2[j-1]:Check if characters match to extend substring

for i in range(1, n+1):Iterate over all indices to find maximum substring length

import java.util.*;

public class LongestCommonSubstringMemo {
    static Map<String, Integer> memo = new HashMap<>();

    public static int lcs(String s1, String s2, int i, int j) {
        if (i == 0 || j == 0) return 0;
        String key = i + "," + j;
        if (memo.containsKey(key)) return memo.get(key);
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            int val = 1 + lcs(s1, s2, i - 1, j - 1);
            memo.put(key, val);
            return val;
        } else {
            memo.put(key, 0);
            return 0;
        }
    }

    public static int longestCommonSubstring(String s1, String s2) {
        int maxLen = 0;
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                int length = lcs(s1, s2, i, j);
                if (length > maxLen) maxLen = length;
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubstring("abcde", "abfce")); // Output: 2
    }
}

Line Notes

static Map<String, Integer> memo = new HashMap<>();Memoization cache to store subproblem results

if (s1.charAt(i - 1) == s2.charAt(j - 1)) {Check character match to extend substring

for (int i = 1; i <= s1.length(); i++) {Iterate over all indices to find max substring length

String key = i + "," + j;Unique key for memoization map

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

unordered_map<string, int> memo;

int lcs(const string& s1, const string& s2, int i, int j) {
    if (i == 0 || j == 0) return 0;
    string key = to_string(i) + "," + to_string(j);
    if (memo.find(key) != memo.end()) return memo[key];
    if (s1[i - 1] == s2[j - 1]) {
        memo[key] = 1 + lcs(s1, s2, i - 1, j - 1);
    } else {
        memo[key] = 0;
    }
    return memo[key];
}

int longestCommonSubstringMemo(const string& s1, const string& s2) {
    int maxLen = 0;
    for (int i = 1; i <= (int)s1.size(); i++) {
        for (int j = 1; j <= (int)s2.size(); j++) {
            int length = lcs(s1, s2, i, j);
            if (length > maxLen) maxLen = length;
        }
    }
    return maxLen;
}

int main() {
    cout << longestCommonSubstringMemo("abcde", "abfce") << endl; // Output: 2
    return 0;
}

Line Notes

unordered_map<string, int> memo;Memo cache to store results of subproblems

if (s1[i - 1] == s2[j - 1]) {Check if characters match to extend substring

for (int i = 1; i <= (int)s1.size(); i++) {Iterate over all indices to find max substring length

string key = to_string(i) + "," + to_string(j);Create unique key for memoization

function longestCommonSubstringMemo(s1, s2) {
    const memo = new Map();
    const n = s1.length, m = s2.length;
    let maxLen = 0;

    function lcs(i, j) {
        if (i === 0 || j === 0) return 0;
        const key = i + ',' + j;
        if (memo.has(key)) return memo.get(key);
        if (s1[i - 1] === s2[j - 1]) {
            const val = 1 + lcs(i - 1, j - 1);
            memo.set(key, val);
            return val;
        } else {
            memo.set(key, 0);
            return 0;
        }
    }

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            const length = lcs(i, j);
            if (length > maxLen) maxLen = length;
        }
    }
    return maxLen;
}

// Test
console.log(longestCommonSubstringMemo('abcde', 'abfce')); // Output: 2

Line Notes

const memo = new Map();Memoization cache to avoid recomputation

if (s1[i - 1] === s2[j - 1]) {Check if characters match to extend substring

for (let i = 1; i <= n; i++) {Iterate over all indices to find max substring length

const key = i + ',' + j;Unique key for memo map

⏱

Complexity

TimeO(n*m) due to memoization avoiding repeated work

SpaceO(n*m) for memoization cache and recursion stack

Each pair (i,j) computed once, total n*m states.

💡 For n=m=1000, about 1 million operations, which is feasible.

Interview Verdict: Accepted but can be improved with bottom-up DP

Better than brute force but recursion overhead and memory usage can be high.

🧠

Bottom-Up DP (Tabulation)

💡 This is the optimal classical DP solution that builds a 2D table iteratively, avoiding recursion overhead and making the solution efficient and clear.

Intuition

Build a 2D dp table where dp[i][j] stores the length of longest common substring ending at s1[i-1] and s2[j-1]. Update max length while filling the table.

Algorithm

1. Initialize a 2D dp array of size (n+1) x (m+1) with zeros.
2. Iterate over i from 1 to n and j from 1 to m.
3. If s1[i-1] == s2[j-1], set dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = 0.
4. Track the maximum dp[i][j] value during iteration.
5. Return the maximum value found.

💡 The zero initialization handles base cases, and the dp table captures all subproblems systematically.

Recurrence:dp[i][j] = dp[i-1][j-1] + 1 if s1[i-1] == s2[j-1] else 0

</>

Code

def longest_common_substring_dp(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    max_len = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
            else:
                dp[i][j] = 0
    return max_len

# Driver code
if __name__ == '__main__':
    print(longest_common_substring_dp('abcde', 'abfce'))  # Output: 2

Line Notes

dp = [[0] * (m + 1) for _ in range(n + 1)]Initialize DP table with zeros for base cases

for i in range(1, n + 1):Iterate over s1 indices starting from 1 for 1-based indexing

if s1[i - 1] == s2[j - 1]:Check if characters match to extend substring

dp[i][j] = dp[i - 1][j - 1] + 1Extend the length of common substring by 1

public class LongestCommonSubstringDP {
    public static int longestCommonSubstring(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n + 1][m + 1];
        int maxLen = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(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;
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubstring("abcde", "abfce")); // Output: 2
    }
}

Line Notes

int[][] dp = new int[n + 1][m + 1];DP table initialized with zeros for base cases

for (int i = 1; i <= n; i++) {Iterate over s1 indices with 1-based indexing

if (s1.charAt(i - 1) == s2.charAt(j - 1)) {Check character match to extend substring

dp[i][j] = dp[i - 1][j - 1] + 1;Extend length of common substring by 1

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int longestCommonSubstringDP(const string& s1, const string& s2) {
    int n = s1.size(), m = s2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    int maxLen = 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] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > maxLen) maxLen = dp[i][j];
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return maxLen;
}

int main() {
    cout << longestCommonSubstringDP("abcde", "abfce") << endl; // Output: 2
    return 0;
}

Line Notes

vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));Initialize DP table with zeros for base cases

for (int i = 1; i <= n; i++) {Iterate over s1 indices with 1-based indexing

if (s1[i - 1] == s2[j - 1]) {Check if characters match to extend substring

dp[i][j] = dp[i - 1][j - 1] + 1;Extend length of common substring by 1

function longestCommonSubstringDP(s1, s2) {
    const n = s1.length, m = s2.length;
    const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
    let maxLen = 0;
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            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;
}

// Test
console.log(longestCommonSubstringDP('abcde', 'abfce')); // Output: 2

Line Notes

const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));Initialize DP table with zeros for base cases

for (let i = 1; i <= n; i++) {Iterate over s1 indices with 1-based indexing

if (s1[i - 1] === s2[j - 1]) {Check character match to extend substring

dp[i][j] = dp[i - 1][j - 1] + 1;Extend length of common substring by 1

⏱

Complexity

TimeO(n*m) due to filling dp table once

SpaceO(n*m) for dp table

Each cell computed once, total n*m cells.

💡 For n=m=1000, about 1 million operations, efficient for interviews.

Interview Verdict: Accepted and recommended approach

This approach balances clarity and efficiency, ideal for interviews.

🧠

Space Optimized Bottom-Up DP (1D DP Array)

💡 This approach reduces space from O(n*m) to O(m) by using a single array and iterating backwards to preserve previous states, making it suitable for large inputs.

Intuition

Since dp[i][j] depends only on dp[i-1][j-1], we can use a 1D array and update it in reverse order to avoid overwriting needed values.

Algorithm

1. Initialize a 1D dp array of length m+1 with zeros.
2. Iterate over s1 indices i from 1 to n.
3. For each i, iterate j from m down to 1 (backwards).
4. If s1[i-1] == s2[j-1], set dp[j] = dp[j-1] + 1; else dp[j] = 0.
5. Track the maximum dp[j] value during iteration.
6. Return the maximum value found.

💡 Backward iteration ensures dp[j-1] from previous iteration is not overwritten before use.

Recurrence:dp[j] = dp[j-1] + 1 if s1[i-1] == s2[j-1] else 0

</>

Code

def longest_common_substring_space_optimized(s1, s2):
    n, m = len(s1), len(s2)
    dp = [0] * (m + 1)
    max_len = 0
    for i in range(1, n + 1):
        for j in range(m, 0, -1):
            if s1[i - 1] == s2[j - 1]:
                dp[j] = dp[j - 1] + 1
                if dp[j] > max_len:
                    max_len = dp[j]
            else:
                dp[j] = 0
    return max_len

# Driver code
if __name__ == '__main__':
    print(longest_common_substring_space_optimized('abcde', 'abfce'))  # Output: 2

Line Notes

dp = [0] * (m + 1)Initialize 1D DP array with zeros for base cases

for i in range(1, n + 1):Iterate over s1 indices

for j in range(m, 0, -1):Iterate backwards over s2 indices to preserve dp[j-1]

dp[j] = dp[j - 1] + 1Extend substring length if characters match

public class LongestCommonSubstringSpaceOpt {
    public static int longestCommonSubstring(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[] dp = new int[m + 1];
        int maxLen = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 1; j--) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[j] = dp[j - 1] + 1;
                    if (dp[j] > maxLen) maxLen = dp[j];
                } else {
                    dp[j] = 0;
                }
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubstring("abcde", "abfce")); // Output: 2
    }
}

Line Notes

int[] dp = new int[m + 1];1D DP array initialized with zeros

for (int i = 1; i <= n; i++) {Iterate over s1 indices

for (int j = m; j >= 1; j--) {Backward iteration over s2 indices to preserve dp[j-1]

dp[j] = dp[j - 1] + 1;Extend substring length if characters match

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int longestCommonSubstringSpaceOpt(const string& s1, const string& s2) {
    int n = s1.size(), m = s2.size();
    vector<int> dp(m + 1, 0);
    int maxLen = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; j--) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[j] = dp[j - 1] + 1;
                if (dp[j] > maxLen) maxLen = dp[j];
            } else {
                dp[j] = 0;
            }
        }
    }
    return maxLen;
}

int main() {
    cout << longestCommonSubstringSpaceOpt("abcde", "abfce") << endl; // Output: 2
    return 0;
}

Line Notes

vector<int> dp(m + 1, 0);Initialize 1D DP array with zeros

for (int i = 1; i <= n; i++) {Iterate over s1 indices

for (int j = m; j >= 1; j--) {Backward iteration to preserve dp[j-1]

dp[j] = dp[j - 1] + 1;Extend substring length if characters match

function longestCommonSubstringSpaceOpt(s1, s2) {
    const n = s1.length, m = s2.length;
    const dp = new Array(m + 1).fill(0);
    let maxLen = 0;
    for (let i = 1; i <= n; i++) {
        for (let j = m; j >= 1; j--) {
            if (s1[i - 1] === s2[j - 1]) {
                dp[j] = dp[j - 1] + 1;
                if (dp[j] > maxLen) maxLen = dp[j];
            } else {
                dp[j] = 0;
            }
        }
    }
    return maxLen;
}

// Test
console.log(longestCommonSubstringSpaceOpt('abcde', 'abfce')); // Output: 2

Line Notes

const dp = new Array(m + 1).fill(0);Initialize 1D DP array with zeros

for (let i = 1; i <= n; i++) {Iterate over s1 indices

for (let j = m; j >= 1; j--) {Backward iteration to preserve dp[j-1]

dp[j] = dp[j - 1] + 1;Extend substring length if characters match

⏱

Complexity

TimeO(n*m) due to nested loops

SpaceO(m) due to 1D dp array

We reduce space by storing only one row at a time, iterating backwards to preserve dependencies.

💡 For large inputs, this saves memory and is still efficient.

Interview Verdict: Accepted and optimal for space

Best approach when memory is constrained or input is large.

📊

All Approaches - One-Glance Tradeoffs

💡 Bottom-up DP (Approach 3) is the best balance of clarity and efficiency for interviews; space optimized (Approach 4) is ideal for large inputs.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^3)	O(1)	No	No	Mention only - never code
2. Top-Down DP with Memoization	O(n*m)	O(n*m)	Yes (deep recursion)	Yes	Good to mention, but bottom-up preferred
3. Bottom-Up DP (Tabulation)	O(n*m)	O(n*m)	No	Yes	Code this in interviews
4. Space Optimized Bottom-Up DP	O(n*m)	O(m)	No	No (without extra tracking)	Mention if asked about optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and definitions (substring vs subsequence).Explain brute force approach to show understanding of problem.Discuss inefficiency and motivate DP.Present top-down memoization to introduce DP concepts.Explain bottom-up DP as optimal solution.Mention space optimization if time permits.Code the bottom-up DP solution carefully.Test with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Understanding of substring vs subsequence, ability to identify overlapping subproblems, DP formulation, coding skills, and optimization awareness.

Common Follow-ups

• How to print the longest common substring itself → track indices during DP.
• Can we solve with suffix trees or suffix automata → mention advanced data structures.

💡 These follow-ups test deeper understanding and knowledge of alternative algorithms.

🔍

Pattern Recognition

When to Use

1) Problem asks for longest matching contiguous substring between two strings; 2) Requires maximum length; 3) Overlapping subproblems exist; 4) Greedy or simple search fails.

Signature Phrases

longest common substringcontiguous sequencemaximum length substring

NOT This Pattern When

Longest Common Subsequence problems which allow non-contiguous matches

Similar Problems

Longest Common Subsequence - similar but allows gapsLongest Palindromic Substring - substring but within one string

Practice

1. You are given a string and need to count all substrings that read the same forwards and backwards. Which approach guarantees an optimal time and space solution for this problem?

easy

A. Use a brute force approach checking every substring with nested loops and palindrome verification.

B. Use a longest common subsequence DP approach comparing the string with its reverse.

C. Expand around each character and each pair of characters to count palindromes in O(n²) time and O(1) space.

D. Apply a greedy approach by extending palindromes only when characters match at the ends.

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all palindromic substrings efficiently, not just longest palindromes.

2. Step 2: Evaluate approaches

   Brute force is correct but inefficient (O(n³)). LCS DP finds longest palindrome but not count of all substrings. Greedy fails on nested palindromes. Expanding around centers counts all palindromes in O(n²) time and O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Expanding around centers covers odd and even length palindromes efficiently [OK]

Hint: Expanding centers counts all palindromes in O(n²) time [OK]

Common Mistakes:

• Confusing longest palindrome with counting all palindromic substrings

2. Given the following code for computing edit distance, what is the value of dp[3] after the inner loop finishes when word1 = 'abc' and word2 = 'ac' during the second iteration of the outer loop (i=2)?

easy

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Trace dp array initialization and first iteration

   Initially dp = [0,1,2]. After i=1 (word1[0]='a'), dp updates to [1,0,1].

2. Step 2: Trace second iteration i=2 (word1[1]='b')

   Start dp[0]=2. For j=1 (word2[0]='a'), chars differ, dp[1]=min(0+1,2+1,1+1)=1. For j=2 (word2[1]='c'), chars differ, dp[2]=min(1+1,1+1,0+1)=1. So dp after inner loop: [2,1,1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual step-by-step matches dp[3]=2 [OK]

Hint: Track dp updates carefully for each i,j iteration [OK]

Common Mistakes:

• Off-by-one indexing
• Confusing prev and temp variables
• Mis-updating dp[0]

3. You are given a string and need to find the length of the longest subsequence that reads the same forwards and backwards. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach selecting matching characters from both ends

B. Sorting the string and then finding the longest common subsequence with the original

C. Divide and conquer by splitting the string into halves and merging results

D. Dynamic Programming using bottom-up tabulation to build solutions for substrings

Solution

1. Step 1: Understand problem requires subsequence, not substring

   Greedy or sorting approaches fail because subsequences can skip characters and order matters.

2. Step 2: Recognize overlapping subproblems and optimal substructure

   Dynamic programming bottom-up tabulation efficiently computes longest palindromic subsequence by building from smaller substrings.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP tabulation is standard for longest palindromic subsequence [OK]

Hint: Longest palindromic subsequence requires DP, not greedy [OK]

Common Mistakes:

• Assuming greedy approach works
• Confusing subsequence with substring
• Trying to sort string for solution

4. You need to determine if a given input string matches a pattern that may include '?' which matches any single character, and '*' which matches any sequence of characters (including empty). Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming that builds a 2D table tracking matches between substrings of input and pattern

B. Pure brute force recursion trying all possible matches without memoization

C. Greedy matching by scanning both strings once, skipping characters when '*' is encountered

D. Sorting both strings and then comparing characters in order

Solution

1. Step 1: Understand problem constraints

   The pattern includes wildcards '?' and '*', which require checking multiple matching possibilities.

2. Step 2: Identify suitable algorithm

   Greedy or sorting approaches fail because '*' can match variable-length substrings; brute force is correct but inefficient. DP efficiently explores all subproblems with memoization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP handles overlapping subproblems and wildcard flexibility [OK]

Hint: Wildcard matching requires DP, not greedy or sorting [OK]

Common Mistakes:

• Assuming greedy works for '*' wildcard
• Confusing brute force with DP
• Thinking sorting helps string matching with wildcards

5. What is the time complexity of the optimal space-optimized dynamic programming solution for counting distinct subsequences of t in s, where m = len(s) and n = len(t)?

medium

A. O(m + n)

B. O(2^m)

C. O(m * n)

D. O(m * n^2)

Solution

1. Step 1: Identify nested loops over s and t

   The code iterates over all characters of s (m times) and for each, iterates over t (n times) in reverse order.

2. Step 2: Calculate total operations

   Each iteration does O(1) work, so total time is O(m * n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two nested loops over lengths m and n -> O(m*n) [OK]

Hint: Nested loops over s and t imply O(m*n) time [OK]

Common Mistakes:

• Confusing recursion exponential time with DP time
• Ignoring nested loop structure