1682. Longest Palindromic Subsequence II

MediumStringDynamic Programming
Leetcode Link

Problem Description

The problem gives us a string s and asks us to find the longest good palindromic subsequence. A good palindromic subsequence is one that:

  • Is a subsequence of the original string.
  • Reads the same forwards and backwards (is a palindrome).
  • Has an even number of characters.
  • Has no two consecutive characters that are the same, except for the middle two characters in the subsequence.

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.

The goal is to calculate the length of this longest subsequence for the provided string.

Intuition

The intuition behind the solution to this problem is derived from classic Dynamic Programming (DP) techniques used in solving palindromic problems, including the Longest Palindromic Subsequence problem.

The idea is to define a recursive function, dfs(i, j, x) to handle the following scenarios:

  • i and j are indices that define the current substring s[i...j] we are considering. Initially, i is 0 (start of the string) and j is len(s)-1 (end of the string).
  • x is the character that we have just included in our subsequence. This is used to ensure that we do not pick the same character again to satisfy the condition of not having two equal consecutive characters.

If s[i] is equal to s[j] and different from x, s[i...j] can contribute to a good palindromic subsequence, and we add 2 to our subsequence count and recurse into the subproblem dfs(i+1, j-1, s[i]).

Otherwise, we cannot pick s[i] and s[j] together. So, we have two options - either skip s[i] or skip s[j], and take the maximum result from these two choices. That is max(dfs(i + 1, j, x), dfs(i, j - 1, x)).

Using caching (@cache decorator from Python’s functools library), we avoid recomputation of the same subproblems, thus, optimizing our solution by storing the results of previous computations.

After the recursive process, we obtain an answer from our dfs function, which is the length of the longest good palindromic subsequence. We then clear the cache to free up memory and return the computed answer.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The implementation uses a top-down approach with memoization, a common technique in dynamic programming. Here's a step-by-step explanation of the algorithm and the various components used in the solution:

  1. Memoization Decorator @cache:

    • The @cache decorator from Python’s functools library is used to automatically memorize the results of the recursive function dfs. This means that any previously computed values for a particular set of arguments will not be recomputed; instead, the cached value will be returned. The function dfs.cache_clear() is used to clear the cache after the main computation is complete to avoid holding onto unnecessary memory references.

  2. Recursive Function dfs(i, j, x):

    • The dfs function is the core of this solution. It takes three parameters: i and j are the indices indicating the subset of the string s we are currently looking at; x is a character that represents the last character that was added to the palindromic subsequence.
    • Base Case: When i >= j, it means that the pointers have crossed each other, or they are at the same position, which implies there are no characters left to consider for the palindromic subsequence. In this scenario, since we are looking for an even-length palindrome, the function returns 0.

  3. Palindrome and Character Condition Check:

    • The condition if s[i] == s[j] and s[i] != x: checks whether the characters at the start and end of our current string subset can be added to form a longer palindrome without violating the rule of not having two identical consecutive characters (other than the middle two in an even-length palindrome).

  4. Processing and Recursion:

    • If the condition is met, we extend our good palindromic subsequence by two (+2, for s[i] and s[j]) and recursively call the function for the next subset dfs(i + 1, j - 1, s[i]).
    • s[i] is passed as the new value of x because it is the character that has just been chosen. We essentially look at the remaining substring inside the current palindrome boundaries, excluding the matching characters.

  5. Exploring Alternate Subsequences:

    • If the above condition does not hold, we have two other possible subsequences to consider. One where we exclude s[i] and another where we exclude s[j]. We recursively call dfs(i + 1, j, x) and dfs(i, j - 1, x) and then select the maximum value as the current result.

  6. Returning the Result:

    • The initial call to the dfs function starts with the full string and an empty string as x to denote that no character has been chosen yet. The final result is the longest length of the good palindromic subsequence obtained.

By this process, we're ensuring that only valid characters are added to the subsequence while maximizing the length by considering all possible subsequences, and we're doing it efficiently by caching intermediate results.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's illustrate the solution approach using a simple example. Consider the string s = "abbad". We want to find the length of the longest good palindromic subsequence.

Here’s a step-by-step walkthrough using the recursive function dfs(i, j, x):

  1. Initial Call: We start with dfs(0, len(s)-1, ''), which means our current string is "abbad" and we haven't chosen any character yet (represented by x = '').

  2. First Recursive Step: Since s[0] ('a') is not equal to s[4] ('d'), we can't choose both, so we need to decide whether to include 'a' or 'd'.

    • We consider two recursive calls: dfs(0 + 1, 4, '') and dfs(0, 4 - 1, '').

  3. Exploring Options:

    • For dfs(1, 4, ''), our current string is "bbad". The first and last characters are 'b' and 'd', which are not the same, so we again have two options: dfs(2, 4, '') and dfs(1, 3, '').

    • For dfs(0, 3, ''), our current string is "abba". Here, the first and last characters are the same, and since x is empty (meaning the last included character isn't 'a'), we can include them in our subsequence, leading to a new call dfs(1, 2, 'a').

  4. Finding a Match:

    • Now, in dfs(1, 2, 'a'), we have the string "bb" which is not allowed since it contains consecutive 'b's, so we can't choose both. We explore dfs(2, 2, 'a') (excluding the first 'b') and dfs(1, 1, 'a') (excluding the second 'b').

  5. Completing the Recursion:

    • When i equals j, we've reached a single character, which cannot form a good palindrome by itself, so in both dfs(2, 2, 'a') and dfs(1, 1, 'a'), the result would be 0.

  6. Backtracking and Picking the Best Option:

    • As we backtrack, we realize that choosing 'a' (from "abba") was the best decision. We add 2 to our count (for the two 'a's), and since we've exhausted the string, the recursion starts returning to the initial call, keeping track of the best length found.

  7. Result: After examining all possibilities, we find that the longest good palindromic subsequence is "abba" with a length of 4.

By caching results along the way, if at any point the same subproblem occurs, the algorithm will fetch the result from the cache, improving efficiency by reducing redundant computations. Finally, we clear the cache to ensure no memory is wasted once we have our result.

Solution Implementation

1from functools import lru_cache
2
3class Solution:
4    def longest_palindrome_subseq(self, s: str) -> int:
5        # Decorator for memoization to optimize the recursive function.
6        @lru_cache(maxsize=None)
7        def dfs(start, end, last_char):
8            # Base case: if pointers cross, no palindrome can be formed.
9            if start >= end:
10                return 0
11          
12            # Recursive case: if characters at start and end match,
13            # and they are different from the last character in the sequence
14            # add 2 to the length (for the two matching characters) and
15            # move both pointers inward.
16            if s[start] == s[end] and s[start] != last_char:
17                return dfs(start + 1, end - 1, s[start]) + 2
18            else:
19                # Recursive case: if the characters don't match,
20                # or are the same as last_char, try removing one character from
21                # either the start or the end and take the max.
22                return max(dfs(start + 1, end, last_char), dfs(start, end - 1, last_char))
23
24        # Call the dfs function with initial values.
25        result = dfs(0, len(s) - 1, '')
26      
27        # Clear the cache after completing the calculation.
28        # This is particularly useful if the method is used multiple times.
29        dfs.cache_clear()
30      
31        # Return the result of the longest palindromic subsequence.
32        return result
33
34# Example usage:
35# sol = Solution()
36# print(sol.longest_palindrome_subseq("bbbab"))  # Output: 4
37
1import java.util.Arrays; // Import Arrays utility for filling the array
2
3class Solution {
4    // Declare a 3D array to memoize the results.
5    private int[][][] memo;
6    // Declare a variable to hold the input string.
7    private String str;
8
9    // Method to find the length of the longest palindromic subsequence.
10    public int longestPalindromeSubseq(String s) {
11        // Length of the string.
12        int n = s.length();
13        // Initialize the string.
14        this.str = s;
15        // Initialize the 3D array with size [n][n][27] and default values -1.
16        memo = new int[n][n][27];
17        for (int[][] l1Array : memo) {
18            for (int[] l2Array : l1Array) {
19                Arrays.fill(l2Array, -1); // Fill second level arrays with -1.
20            }
21        }
22        // Start the depth-first search from the whole string and character 'z' + 1 as the default previous character.
23        return dfs(0, n - 1, 26);
24    }
25
26    // Depth First Search (dfs) to calculate the longest palindromic subsequence.
27    private int dfs(int i, int j, int prevCharIdx) {
28        // Base case: if the start index is greater or equal to the end index, return 0.
29        if (i >= j) {
30            return 0;
31        }
32        // If the result is already computed, return it instead of recomputing.
33        if (memo[i][j][prevCharIdx] != -1) {
34            return memo[i][j][prevCharIdx];
35        }
36        // Initialize result (ans) variable.
37        int ans = 0;
38        // If both characters are the same and different from the previous considered character,
39        // then we can count this pair and move both pointers.
40        if (str.charAt(i) == str.charAt(j) && str.charAt(i) - 'a' != prevCharIdx) {
41            ans = dfs(i + 1, j - 1, str.charAt(i) - 'a') + 2;
42        } else {
43            // Else, try moving either of the pointers to find the longest sequence.
44            ans = Math.max(dfs(i + 1, j, prevCharIdx), dfs(i, j - 1, prevCharIdx));
45        }
46      
47        // Store the computed result in memo array.
48        memo[i][j][prevCharIdx] = ans;
49      
50        // Return the computed longest length.
51        return ans;
52    }
53}
54
1#include <cstring>
2#include <functional>
3#include <algorithm>
4
5class Solution {
6public:
7    int memo[251][251][27]; // Memoization table for dynamic programming
8
9    // The main function to calculate the length of the longest palindromic subsequence
10    int longestPalindromeSubseq(string s) {
11        int n = s.size(); // The length of the string
12        memset(memo, -1, sizeof memo); // Initializes the memoization table to -1
13
14        // Depth-first search function to compute the length of LPS for substring [i, j] with previous character index x
15        // i: start index of substring, j: end index of substring, x: previous character index
16        std::function<int(int, int, int)> dfs = [&](int i, int j, int previousCharIndex) -> int {
17            if (i >= j) return 0; // If the substring length is 0 or 1, no palindrome can be formed
18            if (memo[i][j][previousCharIndex] != -1) return memo[i][j][previousCharIndex]; // If already computed, return the value
19          
20            int longestLength = 0; // Holds the length of the longest palindromic subsequence found
21            // Check if characters at indices i and j are the same and not equal to previousCharIndex
22            // (represented by the corresponding alphabet index)
23            if (s[i] == s[j] && s[i] - 'a' != previousCharIndex)
24                // Characters are the same and not just repetitions from before
25                // Move inward and add two to count for both characters
26                longestLength = dfs(i + 1, j - 1, s[i] - 'a') + 2;
27            else
28                // Characters are different or repeats, take the max after excluding either character
29                longestLength = std::max(dfs(i + 1, j, previousCharIndex), dfs(i, j - 1, previousCharIndex));
30
31            // Store the result in the memo table
32            memo[i][j][previousCharIndex] = longestLength;
33
34            return longestLength; // Return the length found
35        };
36
37        // Start from the full string and with no previous character (26 is used to represent this)
38        return dfs(0, n - 1, 26);
39    }
40};
41
1// Typescript does not support triple size arrays directly, use a Map for memoization instead.
2const memo: Map<string, number> = new Map();
3
4// Utilize a helper function to create the key for our memo map.
5function createMemoKey(i: number, j: number, previousCharIndex: number): string {
6    return `${i}_${j}_${previousCharIndex}`;
7}
8
9// Main function to calculate the length of the longest palindromic subsequence.
10function longestPalindromeSubseq(s: string): number {
11    const n = s.length;  // The length of the string.
12
13    // Function to compute the length of LPS for substring [i, j] with previous character index 'x'.
14    function dfs(i: number, j: number, previousCharIndex: number): number {
15        // Base case: if the substring is of length 0 or 1, no palindrome can be formed.
16        if (i >= j) return 0;
17
18        // Use the helper function to get the key for our memo map.
19        const key = createMemoKey(i, j, previousCharIndex);
20
21        // If already computed, return the value from the memo map.
22        if (memo.has(key)) return memo.get(key)!;
23
24        let longestLength = 0;  // Holds the length of the longest palindromic subsequence found.
25
26        // Check if characters at indices i and j are the same and not equal to previousCharIndex.
27        if (s[i] === s[j] && (s.charCodeAt(i) - 97) !== previousCharIndex) {
28            // Characters are the same and not just repetitions from before.
29            // Move inward and add two to count for both characters.
30            longestLength = dfs(i + 1, j - 1, s.charCodeAt(i) - 97) + 2;
31        } else {
32            // Characters are different or repeats, take the max after excluding either character.
33            longestLength = Math.max(
34                dfs(i + 1, j, previousCharIndex),
35                dfs(i, j - 1, previousCharIndex)
36            );
37        }
38
39        // Store the result in the memo map.
40        memo.set(key, longestLength);
41
42        // Return the length found.
43        return longestLength;
44    }
45
46    // Start from the full string and with no previous character ('26' is used to represent this).
47    return dfs(0, n - 1, 26);
48}
49
Not Sure What to Study? Take the 2-min Quiz

Which of the following shows the order of node visit in a Breadth-first Search?

Time and Space Complexity

The code is a recursive function with memoization to find the length of the longest palindromic subsequence in a string. The function dfs uses memoization through the cache decorator, which means it stores results of subproblems to avoid recomputation.

Time Complexity

The time complexity of the dfs function is O(n^2) where n is the length of the string s. This is because in the worst case, we need to compute the result for each pair of starting and ending indices (i, j) which are n*(n-1)/2 pairs, approximately n^2/2. However, since results are cached, each pair is computed only once. Therefore, we ignore the constant factor and the complexity is O(n^2).

Space Complexity

The space complexity is also O(n^2) due to memoization. The cache needs to store an entry for each unique call to dfs, which, as discussed above, has at most n^2 different argument pairs (i, j, x). The third argument, x, does not significantly increase the number of possible states because it represents the previous character and there are only n possibilities for it. In practice, x is just a character from the input string s, so its impact on the complexity is bounded by the length of s.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«