Longest Common Subsequence

Find the longest sequence of ingredients that appear in the same order in two different recipes. This problem tests dynamic programming skills and the ability to optimize for overlapping subproblems.

dynamic programmingstringsequenceoptimization

Problem Statement

You are given two strings, recipe1 and recipe2, representing two different recipes. Each character in the string represents a unique ingredient. Your task is to find the length of the longest common ingredient sequence that appears in both recipes in the same relative order. Note that ingredients do not need to be consecutive, meaning other ingredients can exist in between. Return the length of this longest common ingredient sequence.

Example 1

Input: {'recipe1': 'ABCDGH', 'recipe2': 'AEDFHR'}

Output: 3

The longest common ingredient sequence is 'ADH', which has a length of 3.

Example 2

Input: {'recipe1': 'AGGTAB', 'recipe2': 'GXTXAYB'}

Output: 4

The longest common ingredient sequence is 'GTAB', which has a length of 4.

Constraints

-1 <= len(recipe1), len(recipe2) <= 1000
-recipe1 and recipe2 contain only uppercase English letters.
-Ingredients are case-sensitive.

Brute Force Approach

The brute force approach involves generating all possible subsequences for both recipes and then comparing them to find the longest common one. Imagine you have two sets of cards, each with ingredients written on them. You'd have to check every possible combination of cards from each set to see which matching set is the longest. This is extremely inefficient because the number of subsequences grows exponentially with the length of the recipes.

TimeO(2^(m+n))

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem