Given two strings 's1' and 's2', find the length of the longest common substring.

Hint

Start with the foundation – the base cases, which are the simplest solutions. Then, layer by layer, use the results of the previous layers to calculate the solutions for the next level. This way, we systematically build up the entire solution, avoiding redundant calculations and ensuring efficiency. It is like building a pyramid.

The underlying calculation logic remains fundamentally identical to the original recursive approach, albeit executed in reverse order.

# Python implementation

def count(s1, s2):
  mx = float('-inf')

  for i in range(len(s2)):
    text = s2[i:]

    for j in range(len(text)):
      target = text[:len(text)-j]

      if target in s1:
        mx = max(mx, len(target))

  return mx
  
s1 = "QuestionOfTheDay"
s2 = "NewQuestion"

print(count(s1, s2))

// Javascript implementation

function count(s1, s2) {
  let max = -Infinity;

  for (let i = 0; i < s2.length; i++) {
    const text = s2.slice(i)

    for (let j = text.length; j >= 0; j--) {
      const target = text.slice(0, j);

      if (s1.includes(target)) {
        max = Math.max(max, target.length);
      }
    }
  }

  return max;
}

const s1 = "QuestionOfTheDay";
const s2 = "NewQuestion";

console.log(count(s1, s2));

Find longest common substring (Tabulation)

Hint