Find length of longest common subsequence
Company: TikTok
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given two strings `s` and `t`, return the **length** of their **longest common subsequence**.
A subsequence is obtained by deleting zero or more characters without changing the relative order of the remaining characters.
### Input
- `s`: string
- `t`: string
### Output
- Integer length of the longest common subsequence of `s` and `t`.
### Constraints (typical)
- `0 <= len(s), len(t) <= 2000`
- Strings consist of lowercase English letters (or ASCII characters).
### Example
- `s = "abcde"`, `t = "ace"` → output `3` (one LCS is `"ace"`).
Quick Answer: This question evaluates understanding of dynamic programming, string algorithms, and algorithmic problem-solving skills related to sequence comparison and the longest common subsequence concept.
Return the length of the longest common subsequence of two strings.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('abcde','ace')
Expected Output: 3
Explanation: ace is a common subsequence.
Input: ('abc','abc')
Expected Output: 3
Explanation: Identical strings have full LCS length.
Input: ('abc','def')
Expected Output: 0
Explanation: No shared characters gives zero.
Input: ('', 'abc')
Expected Output: 0
Explanation: Empty string has LCS length zero.
Hints
- Clarify edge cases before coding.
- Keep outputs deterministic when several valid answers exist.