Longest Palindromic Subsequence
DP on Strings DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Longest Palindromic Subsequence, Dynamic Programming, Subsequences, Palindromes, Longest Common Subsequence, Tabulation, Space Optimization, Time Complexity, Space Complexity, Strings, String Manipulation, Algorithm, space optimization, tabulation, string properties, dynamic programming, Longest Common Subsequence (LCS).
Longest Palindromic Subsequence Problem Statement A palindromic string is a string that reads the same forwards and backwards. Given a string S, find the length of the longest palindromic subsequence of S. 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. Input Specification The input consists of a single line containing a string S. Output Specification Print a single integer representing the length of the longest palindromic subsequence of the given string S. Constraints 1 <= |S| <= 1000 S consists of lowercase English letters. Sample Test Case Input: Output: Explanation: For the input string "bbabcbcab", the longest palindromic subsequence is "babcbab", which has a length of 7. Other palindromic subsequences exist (e.g., "bbb", "bbbb"), but "babcbab" is the longest.