Challenge 2: Longest Common Substring
In this lesson, you will work on an interesting dynamic programming problem, the longest common substring.
We'll cover the following
Problem statement
Given two strings, we want to find the length of the longest substring common in both these strings. For example, if we have two strings, "hello elf"
and "hello yourself"
, we can see two prominent substrings: "hello "
and "elf"
. Since "hello "
is longer, this will be the longest common substring for the given pair of strings.
Input
Your program will take two strings, str1
and str2
, each of length greater than zero as input.
str1 = "hello elf"
str2 = "hello yourself"
Output
Your program should return the length of the longest common substring.
lcs("hello elf", "hello yourself") = 6
lcs("hel", "elf") = 2
Coding challenge
Think about some basic examples to start with and then write a simple recursive algorithm. Slowly build up to the bottom-up solution.
You may check your recursive algorithm by setting stressTesting
to False
. Similarly to check only top-down implementation, set testForBottomUp
to False
. Best of luck!
Get hands-on with 1200+ tech skills courses.