RECUR32 - Editorial

editorial
, , ,
1

Problem Link - Longest Palindromic Subsequence in Recursion

Problem Statement:

Given a string s, your task is to find the length of the longest subsequence that is a palindrome.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

A palindrome is a string/sequence that reads the same backward as forwards, e.g. madam.

Approach:

We are using two pointers, start and end, where start denotes the character at the 0th position, and end denotes the character at the (n-1)th position.

  1. Base Cases:
  • If the start index is greater than the end index, return 0 (no valid subsequence).
  • If the start index equals the end index, return 1 (a single character is a palindrome).
  1. Matching Characters:
  • If the characters at the start and end indices match, add 2 to the result and recurse on the substring between these indices.
  1. Non-Matching Characters:
  • If the characters do not match, recursively explore two options:
    • Exclude the start character.
    • Exclude the end character.
  • Return the maximum length of the subsequences from both options.
  1. Recursion continues until all possible subsequences are explored.

Complexity:

  • Time Complexity: The time complexity of this approach is O(2^n) because every recursive call branches into two subproblems (exploring the start and end characters)
  • Space Complexity: O(n) due to the depth of the recursion stack, where n is the length of the string.