Jobs

Interviews

Discussions

Longest Palindromic Subsequence

Medium

Asked by:

More companies

59 views

Topics:

StringsDynamic Programming

Given a string s, find the longest palindromic subsequence's length in 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.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Constraints:

1 <= s.length <= 1000
s consists only of lowercase English letters.

Try coding it in LeetCode

Longest Palindromic Subsequence

Medium

Asked by:

59 views

Topics:

StringsDynamic Programming

Given a string s, find the longest palindromic subsequence's length in 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.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Constraints:

1 <= s.length <= 1000
s consists only of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string 's'?
Can the input string 's' be empty or null?
Are there any specific character sets that the input string 's' might contain (e.g., only lowercase letters, ASCII characters, Unicode characters)?
If there are multiple palindromic subsequences with the same maximum length, do I need to return a specific one, or is any one acceptable?
Is the input case-sensitive, meaning 'a' and 'A' are considered different characters?

Brute Force Solution

Approach

To find the longest palindromic subsequence using a brute force method, we essentially explore every possible subsequence. This involves generating all possible subsequences and then checking each one to see if it's a palindrome, ultimately picking the longest.

Here's how the algorithm would work step-by-step:

Think of all the possible smaller strings you can make from the original string by removing zero or more characters.
For each of these smaller strings, check if it reads the same forwards and backward (if it's a palindrome).
Keep track of the longest palindrome you find during this process.
After checking all possible smaller strings, the longest one you kept track of is your answer.

Code Implementation

def longest_palindromic_subsequence_brute_force(input_string):
    longest_palindrome = ""

    # Generate all possible subsequences.
    for i in range(1 << len(input_string)):
        subsequence = ""
        for j in range(len(input_string)):
            if (i >> j) & 1:
                subsequence += input_string[j]

        # Check if the subsequence is a palindrome.
        if subsequence == subsequence[::-1]:

            # Update the longest palindrome if necessary.
            if len(subsequence) > len(longest_palindrome):
                longest_palindrome = subsequence

    return longest_palindrome

Big(O) Analysis

Time Complexity

O(2^n * n) – The brute force approach involves generating all possible subsequences of the input string. A string of length n has 2^n possible subsequences because each character can either be included or excluded. For each of these 2^n subsequences, we need to check if it's a palindrome, which takes O(n) time in the worst case (e.g., comparing the first and last characters, then the second and second-to-last, and so on). Therefore, the overall time complexity is O(2^n * n).

Space Complexity

O(1) – The provided brute force approach, focused on generating and checking subsequences, doesn't explicitly create substantial auxiliary data structures. While it iterates through potential subsequences, it primarily manipulates existing characters within the input string and tracks the longest palindrome found so far, likely with a constant number of variables. The space used for these variables (e.g., to store the length and start/end indices of the longest palindrome) remains constant irrespective of the input string's length, N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

Finding the longest palindromic subsequence efficiently involves recognizing overlapping subproblems. We use a table to store and reuse solutions to smaller subproblems, building up to the final answer. This way, we avoid recalculating the same thing multiple times.

Here's how the algorithm would work step-by-step:

Think of the problem in terms of smaller pieces. The longest palindromic subsequence of a long string is related to the longest palindromic subsequences of its smaller parts.
Imagine a table where rows and columns represent different starting and ending positions within the original string.
Start by filling in the table for very short sequences of letters (one or two letters). It's easy to find the longest palindromic subsequence for these.
Now, fill in the table for slightly longer sequences. To do this, look at the values already in the table for the smaller parts of the sequence. Check if the letters at the start and end of the sequence are the same. If they are, this helps you build a longer palindromic subsequence by adding those letters to the subsequence you found in the smaller part.
If the letters at the start and end are different, then the longest palindromic subsequence will be the longer of the two palindromic subsequences you can get by removing either the first or the last letter of the sequence.
Keep going, filling in the table for longer and longer sequences, always using the values you already computed for smaller sequences.
Eventually, you'll fill in the entire table. The value in the table that corresponds to the whole original string will be the length of the longest palindromic subsequence.

Code Implementation

def longest_palindromic_subsequence(input_string):
    string_length = len(input_string)

    # Create a table to store lengths of LPS for subproblems
    dynamic_programming_table = [([0] * string_length) for _ in range(string_length)]

    # Strings of length 1 are palindromes of length 1
    for i in range(string_length):
        dynamic_programming_table[i][i] = 1

    for subsequence_length in range(2, string_length + 1):
        for i in range(string_length - subsequence_length + 1):
            j = i + subsequence_length - 1

            # If the end characters match
            if input_string[i] == input_string[j]:

                #Consider the inner string and add 2 for the matching end characters
                if subsequence_length == 2:
                    dynamic_programming_table[i][j] = 2
                else:
                     dynamic_programming_table[i][j] = dynamic_programming_table[i+1][j-1] + 2

            else:
                # If the end characters do not match, take the maximum of excluding either the left or right character
                dynamic_programming_table[i][j] = max(
                    dynamic_programming_table[i][j-1],
                    dynamic_programming_table[i+1][j])

    # The length of the LPS of the entire string
    return dynamic_programming_table[0][string_length-1]

Big(O) Analysis

Time Complexity

O(n²) – The algorithm uses dynamic programming with a table of size n x n, where n is the length of the input string. Filling each cell in the table requires a constant amount of work involving comparing characters and potentially looking up values in other cells. Since we must fill all n² cells in the table, the time complexity is O(n²).

Space Complexity

O(N^2) – The algorithm uses a table where rows and columns represent starting and ending positions within the original string. This table is used to store the lengths of longest palindromic subsequences for all possible substrings. Since the table is two-dimensional and its dimensions are determined by the length of the input string, N, the space required to store the table is proportional to N * N. Thus the auxiliary space complexity is O(N^2).

Edge Cases

Case	How to Handle
Null or empty string input	Return 0 because there is no subsequence in an empty or null string.
String with a single character	Return 1 because a single character is a palindrome of length 1.
String with two identical characters	Return 2 because the entire string is a palindrome.
String with two different characters	Return 1 because the longest palindromic subsequence is either of the individual characters.
String with all identical characters	Return the length of the string since the entire string is a palindrome.
Long string that is a palindrome	Return the length of the string as it's the longest palindromic subsequence.
Long string with no palindromic subsequences longer than 1	The algorithm should correctly identify this and return 1, as any single character is a palindromic subsequence.
Very long input string exceeding memory capacity	Dynamic programming solutions might lead to memory issues; consider optimizing memory usage or exploring other approaches if the string is exceptionally large (e.g., using iterative DP).

Null or empty string input

How to Handle:

Return 0 because there is no subsequence in an empty or null string.

String with a single character

How to Handle:

Return 1 because a single character is a palindrome of length 1.

String with two identical characters

How to Handle:

Return 2 because the entire string is a palindrome.

String with two different characters

How to Handle:

Return 1 because the longest palindromic subsequence is either of the individual characters.

String with all identical characters

How to Handle:

Return the length of the string since the entire string is a palindrome.

Long string that is a palindrome

How to Handle:

Return the length of the string as it's the longest palindromic subsequence.

Long string with no palindromic subsequences longer than 1

How to Handle:

The algorithm should correctly identify this and return 1, as any single character is a palindromic subsequence.

Very long input string exceeding memory capacity

How to Handle:

Dynamic programming solutions might lead to memory issues; consider optimizing memory usage or exploring other approaches if the string is exceptionally large (e.g., using iterative DP).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string 's'?
Can the input string 's' be empty or null?
Are there any specific character sets that the input string 's' might contain (e.g., only lowercase letters, ASCII characters, Unicode characters)?
If there are multiple palindromic subsequences with the same maximum length, do I need to return a specific one, or is any one acceptable?
Is the input case-sensitive, meaning 'a' and 'A' are considered different characters?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Think of all the possible smaller strings you can make from the original string by removing zero or more characters.
For each of these smaller strings, check if it reads the same forwards and backward (if it's a palindrome).
Keep track of the longest palindrome you find during this process.
After checking all possible smaller strings, the longest one you kept track of is your answer.

Code Implementation

def longest_palindromic_subsequence_brute_force(input_string):
    longest_palindrome = ""

    # Generate all possible subsequences.
    for i in range(1 << len(input_string)):
        subsequence = ""
        for j in range(len(input_string)):
            if (i >> j) & 1:
                subsequence += input_string[j]

        # Check if the subsequence is a palindrome.
        if subsequence == subsequence[::-1]:

            # Update the longest palindrome if necessary.
            if len(subsequence) > len(longest_palindrome):
                longest_palindrome = subsequence

    return longest_palindrome

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think of the problem in terms of smaller pieces. The longest palindromic subsequence of a long string is related to the longest palindromic subsequences of its smaller parts.
Imagine a table where rows and columns represent different starting and ending positions within the original string.
Start by filling in the table for very short sequences of letters (one or two letters). It's easy to find the longest palindromic subsequence for these.
Now, fill in the table for slightly longer sequences. To do this, look at the values already in the table for the smaller parts of the sequence. Check if the letters at the start and end of the sequence are the same. If they are, this helps you build a longer palindromic subsequence by adding those letters to the subsequence you found in the smaller part.
If the letters at the start and end are different, then the longest palindromic subsequence will be the longer of the two palindromic subsequences you can get by removing either the first or the last letter of the sequence.
Keep going, filling in the table for longer and longer sequences, always using the values you already computed for smaller sequences.
Eventually, you'll fill in the entire table. The value in the table that corresponds to the whole original string will be the length of the longest palindromic subsequence.

Code Implementation

def longest_palindromic_subsequence(input_string):
    string_length = len(input_string)

    # Create a table to store lengths of LPS for subproblems
    dynamic_programming_table = [([0] * string_length) for _ in range(string_length)]

    # Strings of length 1 are palindromes of length 1
    for i in range(string_length):
        dynamic_programming_table[i][i] = 1

    for subsequence_length in range(2, string_length + 1):
        for i in range(string_length - subsequence_length + 1):
            j = i + subsequence_length - 1

            # If the end characters match
            if input_string[i] == input_string[j]:

                #Consider the inner string and add 2 for the matching end characters
                if subsequence_length == 2:
                    dynamic_programming_table[i][j] = 2
                else:
                     dynamic_programming_table[i][j] = dynamic_programming_table[i+1][j-1] + 2

            else:
                # If the end characters do not match, take the maximum of excluding either the left or right character
                dynamic_programming_table[i][j] = max(
                    dynamic_programming_table[i][j-1],
                    dynamic_programming_table[i+1][j])

    # The length of the LPS of the entire string
    return dynamic_programming_table[0][string_length-1]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return 0 because there is no subsequence in an empty or null string.
String with a single character	Return 1 because a single character is a palindrome of length 1.
String with two identical characters	Return 2 because the entire string is a palindrome.
String with two different characters	Return 1 because the longest palindromic subsequence is either of the individual characters.
String with all identical characters	Return the length of the string since the entire string is a palindrome.
Long string that is a palindrome	Return the length of the string as it's the longest palindromic subsequence.
Long string with no palindromic subsequences longer than 1	The algorithm should correctly identify this and return 1, as any single character is a palindromic subsequence.
Very long input string exceeding memory capacity	Dynamic programming solutions might lead to memory issues; consider optimizing memory usage or exploring other approaches if the string is exceptionally large (e.g., using iterative DP).

Null or empty string input

How to Handle:

Return 0 because there is no subsequence in an empty or null string.

String with a single character

How to Handle:

Return 1 because a single character is a palindrome of length 1.

String with two identical characters

How to Handle:

Return 2 because the entire string is a palindrome.

String with two different characters

How to Handle:

Return 1 because the longest palindromic subsequence is either of the individual characters.

String with all identical characters

How to Handle:

Return the length of the string since the entire string is a palindrome.

Long string that is a palindrome

How to Handle:

Return the length of the string as it's the longest palindromic subsequence.

Long string with no palindromic subsequences longer than 1

How to Handle:

The algorithm should correctly identify this and return 1, as any single character is a palindromic subsequence.

Very long input string exceeding memory capacity

How to Handle:

Dynamic programming solutions might lead to memory issues; consider optimizing memory usage or exploring other approaches if the string is exceptionally large (e.g., using iterative DP).