Longest Common Subsequence
DP on Strings DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Dynamic Programming on Strings: Longest Common Subsequence (LCS), Dynamic Programming, Strings, Subsequences, Memoization, Tabulation, Space Optimization, Time Complexity, Space Complexity, Recursion, Arrays, Edge Cases, space complexity, dynamic programming, memoization, tabulation, space optimization, recursion, time complexity analysis.
Longest Common Subsequence Problem Statement Given two strings s1 and s2, find the length of their Longest Common Subsequence (LCS). A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. For example, "ace" is a subsequence of "abcde" while "aec" is not. A common subsequence of two strings is a subsequence that is common to both strings. The longest common subsequence is the common subsequence that has the greatest length. Input The input consists of two lines. The first line contains string s1. The second line contains string s2. Output Print a single integer, the length of the Longest Common Subsequence. Constraints 1 <= len(s1), len(s2) <= 1000 s1 and s2 consist of lowercase English letters. Example Input: Output: Explanation: The common subsequences are "c", "d", "cd". The longest among them is "cd", which has a length of 2. Difficulty Medium