Longest Common Substring Explained: Dynamic Programming, TypeScript and Real-World Uses

The Longest Common Substring problem asks us to find the longest contiguous sequence of characters that appears in two strings.

The word contiguous is essential.

Consider:

ABABC
BABCA

The string:

BABC

appears continuously in both inputs.

Therefore:

Longest Common Substring = "BABC"
Length = 4

What is a substring?

A substring contains consecutive characters from the original string.

For:

ABCDE

valid substrings include:

ABC
BCD
DE
C

But:

ACE

is not a substring because its characters are not contiguous.

Another example

Consider:

programming
gaming

A common contiguous section is:

ming

so the longest common substring has length 4.

Brute-force approach

A straightforward solution is to generate every substring of the first string and check whether it appears in the second.

A string of length n has approximately:

n × (n + 1) / 2

substrings.

Testing all of them quickly becomes expensive, so a dynamic-programming approach is usually preferred for standard algorithmic problems.

Dynamic Programming definition

For strings a and b, define:

dp[i][j]

as the length of the longest common substring that ends exactly at a[i - 1] and b[j - 1].

If the two current characters match:

a[i - 1] === b[j - 1]

then:

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

If they do not match:

dp[i][j] = 0

The reset to zero is what enforces contiguity.

Example DP table

For:

a = ABABC
b = BABCA

we obtain conceptually:

      B  A  B  C  A
A     0  1  0  0  1
B     1  0  2  0  0
A     0  2  0  0  1
B     1  0  3  0  0
C     0  0  0  4  0

The largest value is:

4

which corresponds to:

BABC

Why the answer is not necessarily the final cell

The best common substring can end anywhere in the two strings.

For this reason, we maintain a variable such as:

maxLength

while filling the matrix.

TypeScript implementation

function longestCommonSubstringLength(
  a: string,
  b: string
): number {
  const dp: number[][] = Array.from(
    { length: a.length + 1 },
    () => new Array(b.length + 1).fill(0)
  );

  let maxLength = 0;

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        maxLength = Math.max(maxLength, dp[i][j]);
      }
    }
  }

  return maxLength;
}

For:

longestCommonSubstringLength("ABABC", "BABCA");

we get:

4

Returning the actual substring

To return the substring itself, keep track of where the best match ends.

function longestCommonSubstring(
  a: string,
  b: string
): string {
  const dp: number[][] = Array.from(
    { length: a.length + 1 },
    () => new Array(b.length + 1).fill(0)
  );

  let maxLength = 0;
  let endIndex = 0;

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;

        if (dp[i][j] > maxLength) {
          maxLength = dp[i][j];
          endIndex = i;
        }
      }
    }
  }

  return a.slice(endIndex - maxLength, endIndex);
}

Complexity

For string lengths n and m:

Time Complexity:  O(n × m)
Space Complexity: O(n × m)

Every pair of positions is examined once.

Space optimization

The current row depends only on the previous row.

Therefore, the full matrix is unnecessary when only the length is required.

Memory can be reduced to:

O(min(n, m))

Example:

function longestCommonSubstringOptimized(
  a: string,
  b: string
): number {
  if (b.length > a.length) {
    [a, b] = [b, a];
  }

  let previous = new Array(b.length + 1).fill(0);
  let maxLength = 0;

  for (let i = 1; i <= a.length; i++) {
    const current = new Array(b.length + 1).fill(0);

    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        current[j] = previous[j - 1] + 1;
        maxLength = Math.max(maxLength, current[j]);
      }
    }

    previous = current;
  }

  return maxLength;
}

Longest Common Substring vs. Longest Common Subsequence

These problems are frequently confused.

Suppose:

a = ABCDEF
b = ACEF

The Longest Common Subsequence can be:

ACEF

because its characters only need to remain in order.

They do not need to be adjacent.

A common substring, however, must be contiguous. In this example:

EF

is a valid common substring.

Difference in the DP recurrence

For Longest Common Substring, mismatch means:

dp[i][j] = 0

For Longest Common Subsequence, mismatch normally leads to:

dp[i][j] = max(
  dp[i - 1][j],
  dp[i][j - 1]
)

That single difference reflects the requirement that a substring remain continuous.

Text similarity

A long exact contiguous match can be a useful signal when comparing strings or documents.

For example:

customer_relationship_management
relationship_manager

contains a substantial common region.

Longest Common Substring alone is not a complete similarity metric, but it can be one feature in a larger matching system.

CRM and data deduplication

Suppose imported CRM data contains:

Arian Soleimanzadeh Software Engineer
Arian Soleimanzadeh

A large common substring may provide evidence that the records are related.

Production systems should combine this with other signals such as:

• Levenshtein Distance
• Email matching
• Phone matching
• Token similarity
• Data normalization

Bioinformatics

DNA and protein sequences can be treated as strings.

For example:

ACGTACGT
TTGTACGG

contains a long shared contiguous region.

Longest Common Substring concepts can help identify similar local sequence regions, although practical bioinformatics systems often use specialized sequence-alignment algorithms.

Version and sequence comparison

Consider two API paths:

/api/v1/customer/profile
/api/v2/customer/profile

A large common region is:

/customer/profile

Common-substring logic can therefore be useful as a building block in sequence comparison tools.

Plagiarism and document similarity

Long identical segments between documents can provide a signal for copied or repeated content.

Real plagiarism-detection systems generally combine this idea with tokenization, N-grams, fingerprinting, and semantic techniques.

Log and security analysis

Consider:

ERROR_AUTH_TOKEN_EXPIRED_USER_101
ERROR_AUTH_TOKEN_EXPIRED_USER_205

A long common segment can help identify that the entries belong to the same underlying error pattern.

Multiple optimal answers

There may be several longest common substrings with the same length.

For example:

a = abcXYZ123
b = abcABC123

both:

abc
123

have length 3.

If every answer is needed, store the end positions of all cells whose value equals the maximum.

Edge cases

Important cases include:

• One empty string
• No common characters
• Identical strings
• Multiple equally long matches
• Case-sensitive versus case-insensitive comparison

For case-insensitive matching, normalize the input before running the algorithm.

Common interview question

A typical problem asks:

Given two strings, find the length or value of their longest common substring.

A good explanation should cover:

1. The substring must be contiguous.
2. dp[i][j] represents a match ending at the current positions.
3. A mismatch resets the current match to zero.
4. A global maximum must be maintained.
5. Time complexity is O(n × m).
6. Memory can be optimized if necessary.

Common mistake: using the LCS recurrence

Writing:

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

on mismatch solves the Longest Common Subsequence problem, not Longest Common Substring.

For substring matching, the correct mismatch behavior is:

dp[i][j] = 0

Are faster algorithms possible?

Yes.

For very large input sizes, advanced structures such as:

• Suffix Trees
• Suffix Arrays
• Suffix Automata

can provide more efficient solutions.

However, Dynamic Programming remains one of the clearest approaches for learning, interviews, and moderate input sizes.

Conclusion

The Longest Common Substring problem finds the longest contiguous sequence shared by two strings.

Its core recurrence is:

if a[i - 1] === b[j - 1]
    dp[i][j] = dp[i - 1][j - 1] + 1
else
    dp[i][j] = 0

The standard solution uses:

Time:  O(n × m)
Space: O(n × m)

with memory optimization down to:

O(min(n, m))

The key idea to remember is simple:

A substring must remain continuous, so any mismatch breaks the current matching chain.