Understanding the Problem
We are given two strings: s1
and s2
. Our goal is to find the longest common substring shared between them.
A substring means characters must be consecutive and appear in the same order in both strings.
For example, in s1 = "abcde"
and s2 = "abfce"
, the common substrings are "a", "b", and "e". The longest among them is of length 1.
Step-by-Step Solution with Example
Step 1: Choose a strategy
We'll use a technique called Dynamic Programming. It helps us solve problems by breaking them down into smaller overlapping subproblems and storing their solutions.
Step 2: Initialize a 2D array
We create a 2D array dp
where dp[i][j]
represents the length of the longest common substring ending at s1[i-1]
and s2[j-1]
.
This array has dimensions (len(s1)+1)
x (len(s2)+1)
, and we initialize it with 0s.
Step 3: Define variables to track the result
We keep:
maxLen = 0
– to store the length of the longest substring found so far
endIndex = 0
– to remember where that substring ends in s1
Step 4: Loop through characters of both strings
We loop through i
from 1 to len(s1)
, and inside that, loop through j
from 1 to len(s2)
.
Step 5: Compare characters
If s1[i-1] == s2[j-1]
, it means we can extend the previous matching substring, so we do:
dp[i][j] = dp[i-1][j-1] + 1
Step 6: Update the maximum length and position
If this newly found substring is longer than any previous one, update maxLen
and endIndex
:
if dp[i][j] > maxLen:
maxLen = dp[i][j]
endIndex = i
Step 7: Extract the final result
Once we've filled the dp
table, we extract the substring from s1
:
longest_substring = s1[endIndex - maxLen : endIndex]
Example:
s1 = "abcdf"
, s2 = "abedf"
The common substrings are "ab" and "df". The longest is "ab" (length 2).
The 2D dp
table helps track where the substrings match and how long they are.
Edge Cases
- Empty strings: If either
s1
or s2
is empty, return 0
.
- No common substring: If no characters match consecutively, return
0
.
- Full match: If the strings are identical, return the full string as the result.
- Multiple same-length substrings: Return any one of them (most implementations return the one that appears first in
s1
).
Comments
Loading comments...