Longest Shared Subsequence (Medium) — Practice with Code Visualizer

You are given two strings, str1 and str2. Your task is to determine the length of their longest shared subsequence.

A subsequence is a sequence derived from another string by deleting zero or more characters without altering the relative order of the remaining characters. For instance, "cdf" is a subsequence of "abcdef" because you can obtain it by removing 'a', 'b', and 'e'.

A shared subsequence of two strings is a subsequence that appears in both strings. The goal is to find the maximum possible length of such a shared subsequence.

If no characters are shared between the two strings (i.e., no common subsequence exists), return 0.

Key Observations:

The subsequence does not need to occupy consecutive positions in either string.
The order of characters in the subsequence must be preserved as they appear in both original strings.
Characters can be skipped, but never rearranged.

The longest shared subsequence is "ace", which has a length of 3. We can form "ace" from "abcde" by removing 'b' and 'd', and "ace" from "ace" by removing nothing.

When both strings are identical, the entire string is the longest shared subsequence. Here, "abc" is common to both with length 3.

The two strings share no common characters whatsoever. Therefore, no shared subsequence exists, and the result is 0.