Loading problem...
Given a string s, determine the length of the longest symmetric subsequence that can be extracted from it.
A subsequence is a sequence formed by removing zero or more characters from the original string while preserving the relative order of the remaining characters. A symmetric subsequence (also known as a mirror sequence) reads the same forwards and backwards.
Your task is to find the maximum length of such a symmetric subsequence that exists within the given string.
Key Insight: Unlike substrings (which must be contiguous), subsequences allow skipping characters. This means you can select characters from various positions in the string, as long as their relative order is preserved, to form the longest possible sequence that mirrors itself.
For example, in the string "character", you could form the symmetric subsequence "carac" by selecting characters at positions 0, 2, 4, 5, 7 (c-a-r-a-c), which reads the same in both directions.
s = "bbbab"4The longest symmetric subsequence is "bbbb". We can extract all four 'b' characters (at positions 0, 1, 2, 4) to form a sequence that reads the same forwards and backwards. Although we skip the 'a' at position 3, the remaining characters maintain their relative order.
s = "cbbd"2The longest symmetric subsequence is "bb". The two adjacent 'b' characters form a palindrome of length 2. While each individual character is technically a palindrome of length 1, "bb" is the longest achievable symmetric sequence in this string.
s = "racecar"7The entire string "racecar" is already symmetric (it reads the same forwards and backwards), so the longest symmetric subsequence has length 7—the entire string itself. When the input is already a palindrome, no characters need to be removed.
Constraints