Longest Common Subsequence

[jsartisan]

Info

difficulty: medium
title: Longest Common Subsequence
type: question
template: typescript
tags: javascript, blind75, dynamic-programming, string

Question

Given two strings text1 and text2, find the length of their longest common subsequence.

Rules:

• Subsequence can skip characters (doesn't need to be contiguous)
• Must maintain relative order of characters
• Common subsequence must exist in both strings
• Return 0 if no common subsequence exists

Constraints:

• 1 ≤ text1.length, text2.length ≤ 1000
• Strings contain only lowercase English letters

Examples:

// Example 1:
console.log(longestCommonSubsequence("cat", "crabt"));
// Output: 3
// Explanation: "cat" is common subsequence

// Example 2:
console.log(longestCommonSubsequence("abcd", "abcd"));
// Output: 4
// Explanation: Entire string is common

// Example 3:
console.log(longestCommonSubsequence("abcd", "efgh"));
// Output: 0
// Explanation: No common subsequence

Template

index.ts

export function longestCommonSubsequence(text1: string, text2: string): number {

}

index.test.ts

import { longestCommonSubsequence } from './index';

describe('longestCommonSubsequence', () => {
  test('Example 1: Subsequence exists', () => {
    expect(longestCommonSubsequence("cat", "crabt")).toBe(3);
  });

  test('Example 2: Identical strings', () => {
    expect(longestCommonSubsequence("abcd", "abcd")).toBe(4);
  });

  test('Example 3: No common subsequence', () => {
    expect(longestCommonSubsequence("abcd", "efgh")).toBe(0);
  });

  test('Single character strings', () => {
    expect(longestCommonSubsequence("a", "a")).toBe(1);
  });

  test('Different length strings', () => {
    expect(longestCommonSubsequence("abc", "ac")).toBe(2);
  });

  test('Partial match', () => {
    expect(longestCommonSubsequence("abc", "def")).toBe(0);
  });

  test('Multiple possible subsequences', () => {
    expect(longestCommonSubsequence("abcde", "ace")).toBe(3);
  });

  test('Repeated characters', () => {
    expect(longestCommonSubsequence("aaaa", "aa")).toBe(2);
  });

  test('Complex sequence', () => {
    expect(longestCommonSubsequence("abcdef", "acf")).toBe(3);
  });

  test('Long strings', () => {
    expect(longestCommonSubsequence("abcdefghij", "acebdfi")).toBe(6);
  });
});

[github-actions[bot]]

306 - Pull Request updated.