Longest Palindromic Subsequence - Microsoft Online Assessment

Problem Preview

"Given a string "s" consisting only of lowercase English letters, find the length of its Longest Palindromic Subsequence (LPS). A subsequence is obtained by deleting zero or more characters from the string while preserving the relative order of the remaining characters. The selected characters do not need to be contiguous. A palindrome reads the same from left to right and right to left. Examples Input| Output ""ba""| "1" ""aaa""| "3" ""bandana""| "5" Example 1 For: s = "ba" Possible palindromic subsequences include: "b" "a" Hence, the longest palindromic subsequence has length: 1 Example 2 For: s = "aaa" The entire string is already a palindrome: "aaa" Therefore: Answer = 3 Example 3 For: s = "bandana" One longest palindromic subsequence is: "anana" Therefore: Answer = 5 Constraints - "1 ≤ n ≤ 5000" - "s" contains only lowercase English letters. Expected Complexity The intended solution should run in: Time: O(n²) Space: O(n) An "O(n²)" space solution may be possible using the standard interval DP, but the preferred solution should optimize the memory usage to O(n). Output Return a single integer representing the length of the Longest Palindromic Subsequence of "s"."