Challenge 2: Longest Common Substring

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!