How to find Longest Common Substring?

Let's dive in!

Given two strings, the task is to find longest common substring, in same order, present in given strings. Remember that a substring is a sequence of characters that appears consecutively within a string.

Problem Statement

Let's take an example to understand the problem better.

Input s1: “dadef”  s2: “adwce”  Output: 2  Explanation: Substring “ad” of length 2 is the longest.

Are you curious about the different approaches to find out the longest common substring? Let's dive in and explore them together!

The simple approach checks for every substring of sequence 1 whether it is also a substring in sequence 2.

Simple Approach

The recursive strategy involves repeatedly comparing characters of both sequences, and maximize the match if they are identical.

Recursive Approach

Time complexity: O(3 ^(n*m)), where n and m are lengths of sequences.  Space complexity: O(max(n, m))

The optimal approach is to employ dynamic programming of storing sub-problems. This entails determining the longest common suffix for all sub-strings in both sequences.

Dynamic Programming Approach

Time complexity: O(n*m), where n and m are the lengths of sequences.  Space complexity: O(n*m)

Want to explore these approaches and learn how to implement them in various programming languages?

Click on the link below to start your journey.