Longest Common Subsequence

Difficulty: Medium | Category: Dynamic Programming | Asked at: Google, Meta, Amazon | Platform: Unfoldd Arena

**Longest Common Subsequence** ================================ **Problem Statement** ------------------- Given two strings `X` and `Y`, find the length of their **Longest Common Subsequence (LCS)**. A **Longest Common Subsequence** is a sequence that appears in the same order in both `X` and `Y` and has no common elements other than those from `X` and `Y`. This means that the sequence should not be a subset of another string within `X` or `Y`. **Rules and Constraints** ------------------------- * The input strings `X` and `Y` are of arbitrary length and comprise alphanumeric characters only. * The output is an integer representing the length of the Longest Common Subsequence. * Time and space complexity constraints: * Time complexity: O(m*n) where `m` and `n` are the lengths of `X` and `Y`, respectively. This is because we will be using a 2D array to store the dynamic programming table, and we need to iterate over each character in both strings once. * Space complexity: O(m*n) to store the dynamic programming table. **Requirements** --------------- Your solution should be written in a programming language supported by our platform. It should be a standalone function that takes two string parameters, `X` and `Y`, and returns an integer representing the length of the Longest Common Subsequence. ### Example **Input:** {"input_data":[1,2,3]} **Output:** [1,2,3]

Solve Longest Common Subsequence online for free in Python, JavaScript, Java, C++, TypeScript, Go, Rust, PHP, Swift, Kotlin, Dart, Ruby, C, and C#. Practice Medium level coding interview problems with instant test case evaluation and AI-powered analysis.

Keywords: Longest Common Subsequence solution, Longest Common Subsequence leetcode, Longest Common Subsequence python, Longest Common Subsequence javascript,Longest Common Subsequence java, Longest Common Subsequence approach, how to solve Longest Common Subsequence, medium coding problems, Dynamic Programming problems, coding interview preparation, DSA practice free.

Longest Common Subsequence

Medium

Longest Common Subsequence

Problem Statement

Given two strings

X
and
Y
, find the length of their Longest Common Subsequence (LCS).

A Longest Common Subsequence is a sequence that appears in the same order in both

X
and
Y
and has no common elements other than those from
X
and
Y
. This means that the sequence should not be a subset of another string within
X
or
Y
.

Rules and Constraints

  • The input strings
    X
    and
    Y
    are of arbitrary length and comprise alphanumeric characters only.
  • The output is an integer representing the length of the Longest Common Subsequence.
  • Time and space complexity constraints:
    • Time complexity: O(m*n) where
      m
      and
      n
      are the lengths of
      X
      and
      Y
      , respectively. This is because we will be using a 2D array to store the dynamic programming table, and we need to iterate over each character in both strings once.
    • Space complexity: O(m*n) to store the dynamic programming table.

Requirements

Your solution should be written in a programming language supported by our platform. It should be a standalone function that takes two string parameters,

X
and
Y
, and returns an integer representing the length of the Longest Common Subsequence.

Example

Input: {"input_data":[1,2,3]} Output: [1,2,3]

CompaniesGoogleMetaAmazon
JavaScript

Login to write code

Solve problems, verify your skills, and earn XP.