How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Roku.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Roku during technical interviews.

Compute longest common subsequence length

Q: Compute longest common subsequence length

This question evaluates understanding of dynamic programming and sequence processing, measuring competence in reasoning about optimal substructure, overlapping subproblems, and algorithmic complexity.

Company: Roku

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem You are given two strings `s` and `t`. A **subsequence** of a string is obtained by deleting zero or more characters without changing the order of the remaining characters. Return the **length** of the **longest common subsequence (LCS)** between `s` and `t`. ## Input - Two strings `s`, `t` ## Output - An integer: the length of the LCS of `s` and `t` ## Constraints (typical interview bounds) - `0 <= len(s), len(t) <= 1000` - Strings contain lowercase/uppercase letters (assume ASCII letters) ## Examples - `s = "abcde"`, `t = "ace"` → output `3` (LCS could be `"ace"`) - `s = "abc"`, `t = "def"` → output `0`

Quick Answer: This question evaluates understanding of dynamic programming and sequence processing, measuring competence in reasoning about optimal substructure, overlapping subproblems, and algorithmic complexity.

You are given two strings `s` and `t`. A **subsequence** of a string is obtained by deleting zero or more characters without changing the order of the remaining characters. Return the **length** of the **longest common subsequence (LCS)** between `s` and `t`. ### Input - Two strings `s`, `t`. ### Output - An integer: the length of the LCS of `s` and `t`. ### Examples - `s = "abcde"`, `t = "ace"` → `3` (LCS could be `"ace"`) - `s = "abc"`, `t = "def"` → `0`

Constraints

0 <= len(s), len(t) <= 1000
Strings contain ASCII letters (lowercase/uppercase)

Examples

Input: ("abcde", "ace")

Expected Output: 3

Explanation: The LCS is "ace" with length 3.

Input: ("abc", "def")

Expected Output: 0

Explanation: No characters are common, so the LCS length is 0.

Input: ("abc", "abc")

Expected Output: 3

Explanation: Identical strings share the whole string as a subsequence.

Input: ("", "abc")

Expected Output: 0

Explanation: An empty string shares no subsequence, so the length is 0.

Input: ("", "")

Expected Output: 0

Explanation: Two empty strings have an empty LCS of length 0.

Input: ("bl", "yby")

Expected Output: 1

Explanation: Only 'b' is common, giving LCS length 1.

Input: ("abcba", "abcbcba")

Expected Output: 5

Explanation: The LCS "abcba" has length 5.

Input: ("AGGTAB", "GXTXAYB")

Expected Output: 4

Explanation: The LCS is "GTAB" with length 4.

Hints

Define dp[i][j] = length of the LCS of the first i characters of s and the first j characters of t.
If s[i-1] == t[j-1], then dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
The base cases (empty prefix on either side) are all 0, so initialize the first row and column to 0.
Space can be reduced to O(min(m, n)) by keeping only the previous and current rows.

Quick Overview

This question evaluates understanding of dynamic programming and sequence processing, measuring competence in reasoning about optimal substructure, overlapping subproblems, and algorithmic complexity.