Jobs

Interviews

Discussions

Longest Palindromic Subsequence After at Most K Operations

Medium

Asked by:

25 views

Topics:

StringsDynamic Programming

You are given a string s and an integer k.

In one operation, you can replace the character at any position with the next or previous letter in the alphabet (wrapping around so that 'a' is after 'z'). For example, replacing 'a' with the next letter results in 'b', and replacing 'a' with the previous letter results in 'z'. Similarly, replacing 'z' with the next letter results in 'a', and replacing 'z' with the previous letter results in 'y'.

Return the length of the longest palindromic subsequence of s that can be obtained after performing at most k operations.

Example 1:

Input: s = "abced", k = 2

Output: 3

Explanation:

Replace s[1] with the next letter, and s becomes "acced".
Replace s[4] with the previous letter, and s becomes "accec".

The subsequence "ccc" forms a palindrome of length 3, which is the maximum.

Example 2:

Input: s = "aaazzz", k = 4

Output: 6

Explanation:

Replace s[0] with the previous letter, and s becomes "zaazzz".
Replace s[4] with the next letter, and s becomes "zaazaz".
Replace s[3] with the next letter, and s becomes "zaaaaz".

The entire string forms a palindrome of length 6.

Constraints:

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

Try coding it in LeetCode

Longest Palindromic Subsequence After at Most K Operations

Medium

Asked by:

25 views

Topics:

StringsDynamic Programming

You are given a string s and an integer k.

Return the length of the longest palindromic subsequence of s that can be obtained after performing at most k operations.

Example 1:

Input: s = "abced", k = 2

Output: 3

Explanation:

Replace s[1] with the next letter, and s becomes "acced".
Replace s[4] with the previous letter, and s becomes "accec".

The subsequence "ccc" forms a palindrome of length 3, which is the maximum.

Example 2:

Input: s = "aaazzz", k = 4

Output: 6

Explanation:

Replace s[0] with the previous letter, and s becomes "zaazzz".
Replace s[4] with the next letter, and s becomes "zaazaz".
Replace s[3] with the next letter, and s becomes "zaaaaz".

The entire string forms a palindrome of length 6.

Constraints:

1 <= s.length <= 200
1 <= k <= 200
s consists of only 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 are the constraints on the length of the input string and the value of 'k'?
Is 'k' guaranteed to be non-negative?
If multiple longest palindromic subsequences can be achieved with at most 'k' operations, should I return any one of them, or is there a specific preference?
What should I return if the input string is null or empty?
What characters will the input string contain (e.g., only lowercase letters, ASCII characters, Unicode characters)?

Brute Force Solution

Approach

To find the longest palindromic sequence, we'll try every single possible combination of changes to the original sequence, within the allowed number of changes. Then, for each of these possibilities, we check if the modified sequence is a palindrome and keep track of the longest one we find.

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

Consider every possible subsequence of the given sequence.
For each subsequence, try all possible ways to make changes to the sequence, up to the maximum allowed number of changes.
For each changed sequence, check if it's a palindrome.
If the changed sequence is a palindrome, calculate its length.
Compare its length with the length of the longest palindrome found so far.
If the new palindrome is longer, save it as the longest palindrome.
After checking all possible subsequences and changes, return the longest palindrome found.

Code Implementation

def longest_palindromic_subsequence_after_k_operations_brute_force(sequence, max_changes):

    longest_palindrome = ""

    for i in range(1 << len(sequence)):
        subsequence = ""
        for j in range(len(sequence)):
            if (i >> j) & 1:
                subsequence += sequence[j]

        # Iterate through all possible changes to the subsequence
        for j in range(len(subsequence) + 1):
            for k in range(len(subsequence) + 1):
                for l in range(len(subsequence) + 1):
                    for m in range(len(subsequence) + 1):
                        for n in range(len(subsequence) + 1):
                            modified_subsequence = list(subsequence)
                            number_of_changes = 0

                            if j < len(subsequence) and number_of_changes < max_changes:
                                modified_subsequence[j] = 'a' if modified_subsequence[j] != 'a' else 'b'
                                number_of_changes += 1
                            if k < len(subsequence) and number_of_changes < max_changes:
                                modified_subsequence[k] = 'c' if modified_subsequence[k] != 'c' else 'a'
                                number_of_changes += 1
                            if l < len(subsequence) and number_of_changes < max_changes:
                                modified_subsequence[l] = 'b' if modified_subsequence[l] != 'b' else 'c'
                                number_of_changes += 1
                            if m < len(subsequence) and number_of_changes < max_changes:
                                modified_subsequence[m] = 'a' if modified_subsequence[m] != 'a' else 'c'
                                number_of_changes += 1
                            if n < len(subsequence) and number_of_changes < max_changes:
                                modified_subsequence[n] = 'b' if modified_subsequence[n] != 'b' else 'a'
                                number_of_changes += 1

                            modified_subsequence = "".join(modified_subsequence)

                            # Only consider the subsequence if it's a palindrome
                            if modified_subsequence == modified_subsequence[::-1]:

                                # Update the longest palindrome found so far
                                if len(modified_subsequence) > len(longest_palindrome):
                                    longest_palindrome = modified_subsequence
    return longest_palindrome

Big(O) Analysis

Time Complexity

O(2^(2n)) – The algorithm considers every possible subsequence, which is 2^n. For each subsequence, it tries all possible ways to make changes up to K changes. In the worst case, K could be close to n. Trying every change is exponential. Then for each modified subsequence (again, potentially of length n), it checks if it's a palindrome. The palindrome check is O(n). However, the dominant cost is generating and modifying all the subsequences. Since subsequence generation is O(2^n) and applying all possible <=K changes makes the whole algorithm O(2^(2n)).

Space Complexity

O(N*2^N) – The provided solution iterates through every possible subsequence, which can be 2^N in the worst case, where N is the length of the input sequence. For each subsequence, it tries all possible ways to make changes, implicitly creating modified versions of the subsequence, requiring space proportional to the subsequence's length (at most N). The storage for the longest palindrome found so far also uses space proportional to N. Thus, in the worst case, the algorithm potentially stores all 2^N subsequences, each of size at most N, leading to O(N * 2^N) space complexity due to the storage of modified subsequence and longest palindrome.

Optimal Solution

Approach

This problem asks us to find the longest palindrome we can make from a given sequence by changing at most a certain number of characters. The core idea is to use dynamic programming to efficiently determine the length of the longest palindromic subsequence considering possible changes to the sequence.

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

Think about palindromes: A palindrome reads the same forward and backward. We want to find the longest one that we can make from the given sequence.
Consider the ends of the sequence: If the characters at the start and end of the sequence are the same, they can both be part of the palindromic subsequence.
If the characters are different, we need to use an operation to make them the same or skip either the beginning or the end of the sequence. Because we can perform a limited number of operations, we will check how many operations we will use in our solution.
Use a table to store results: Build a table where each cell represents the longest palindromic subsequence for a specific part of the sequence. The table stores the length of the palindromic subsequence and the number of operations used to build the subsequence.
Fill the table diagonally: Start filling the table from the shortest subsequences to the longest ones. For each subsequence, check if the ends match. If they do, add 2 to the length of the inner subsequence's palindrome. If they don't match, consider changing one end to match the other and increment the operations used.
Choose the best option: For each subsequence, check all the possible answers using the values already calculated and pick the one that gives you the longest palindromic subsequence using at most the maximum number of operations allowed. When the ends don't match, compare the lengths when skipping either beginning or ending.
The final answer: The value in the table cell that represents the entire sequence will contain the length of the longest palindromic subsequence that can be created with at most K operations.

Code Implementation

def longest_palindrome_subsequence_after_k_operations(sequence, max_operations):
    sequence_length = len(sequence)
    
    # Initialize DP table: dp[i][j] = (length, operations)
    dp_table = [[(0, 0) for _ in range(sequence_length)] for _ in range(sequence_length)]

    # Base case: single characters are palindromes with 0 operations
    for i in range(sequence_length):
        dp_table[i][i] = (1, 0)

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

            # If the ends match, extend the inner palindrome
            if sequence[i] == sequence[j]:
                dp_table[i][j] = (dp_table[i+1][j-1][0] + 2, dp_table[i+1][j-1][1])

            # If they don't match, consider changing characters or skipping
            else:
                length_without_beginning,
                operations_without_beginning = dp_table[i+1][j]
                
                length_without_ending,
                operations_without_ending = dp_table[i][j-1]

                # Determine which choice creates
                # the longer palindromic subsequence
                if length_without_beginning > length_without_ending:
                    longest_subsequence_length = length_without_beginning
                    operations_needed = operations_without_beginning
                else:
                    longest_subsequence_length = length_without_ending
                    operations_needed = operations_without_ending
                    
                # Check if using an operation to match
                # chars results in a longer subsequence
                length_with_operation,
                operations_with_operation = dp_table[i+1][j-1]
                
                if operations_with_operation < max_operations and \
                   length_with_operation + 2 > longest_subsequence_length :
                        longest_subsequence_length = length_with_operation + 2
                        operations_needed = operations_with_operation + 1

                #Store the result in the DP table
                dp_table[i][j] = (longest_subsequence_length, operations_needed)

    #The top-right cell contains the result
    return dp_table[0][sequence_length-1][0]

Big(O) Analysis

Time Complexity

O(n²) – The dynamic programming approach utilizes a table of size n x n, where n is the length of the input sequence. Filling this table involves iterating through all possible sub-sequences, which requires nested loops. The outer loop considers the starting index, and the inner loop considers the ending index for each sub-sequence. Consequently, the time complexity is determined by the number of cells in the table, leading to approximately n*n operations, which simplifies to O(n²).

Space Complexity

O(N*N) – The solution uses a table (dynamic programming table) to store the results, where each cell represents the longest palindromic subsequence for a specific part of the sequence along with the number of operations used. This table has dimensions related to the length of the input sequence. If the input sequence has a length of N, then the table will have N rows and N columns to cover all possible subsequences. Therefore, the auxiliary space required is proportional to N*N, which simplifies to O(N*N).

Edge Cases

Case	How to Handle
Null or empty string input	Return 0, as the longest palindromic subsequence has length 0.
String of length 1	Return 1, as a single character is a palindrome of length 1.
String of length 2	If the characters are equal, return 2; otherwise, if k > 0 return 2, else return 1.
String with all identical characters and K=0	Return the length of the string directly, as it is already a palindrome.
String with all identical characters and K > 0	Return the length of the string directly, as it is already a palindrome.
K is greater or equal to the length of the string	Return the length of the string, since we can make all characters equal.
Large input string and large K, potential for integer overflow during calculations	Use appropriate data types (e.g., long long) for storing intermediate results to prevent overflow.
String with no palindromic subsequence without operations and K=0	The length of longest palindromic subsequence is still calculated correctly based on matching pairs or single character selections if the string is not a palindrome and k=0

Null or empty string input

How to Handle:

Return 0, as the longest palindromic subsequence has length 0.

String of length 1

How to Handle:

Return 1, as a single character is a palindrome of length 1.

String of length 2

How to Handle:

If the characters are equal, return 2; otherwise, if k > 0 return 2, else return 1.

String with all identical characters and K=0

How to Handle:

Return the length of the string directly, as it is already a palindrome.

String with all identical characters and K > 0

How to Handle:

Return the length of the string directly, as it is already a palindrome.

K is greater or equal to the length of the string

How to Handle:

Return the length of the string, since we can make all characters equal.

Large input string and large K, potential for integer overflow during calculations

How to Handle:

Use appropriate data types (e.g., long long) for storing intermediate results to prevent overflow.

String with no palindromic subsequence without operations and K=0

How to Handle:

The length of longest palindromic subsequence is still calculated correctly based on matching pairs or single character selections if the string is not a palindrome and k=0

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 are the constraints on the length of the input string and the value of 'k'?
Is 'k' guaranteed to be non-negative?
If multiple longest palindromic subsequences can be achieved with at most 'k' operations, should I return any one of them, or is there a specific preference?
What should I return if the input string is null or empty?
What characters will the input string contain (e.g., only lowercase letters, ASCII characters, Unicode characters)?

Brute Force Solution

Approach

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

Consider every possible subsequence of the given sequence.
For each subsequence, try all possible ways to make changes to the sequence, up to the maximum allowed number of changes.
For each changed sequence, check if it's a palindrome.
If the changed sequence is a palindrome, calculate its length.
Compare its length with the length of the longest palindrome found so far.
If the new palindrome is longer, save it as the longest palindrome.
After checking all possible subsequences and changes, return the longest palindrome found.

Code Implementation

def longest_palindromic_subsequence_after_k_operations_brute_force(sequence, max_changes):

    longest_palindrome = ""

    for i in range(1 << len(sequence)):
        subsequence = ""
        for j in range(len(sequence)):
            if (i >> j) & 1:
                subsequence += sequence[j]

        # Iterate through all possible changes to the subsequence
        for j in range(len(subsequence) + 1):
            for k in range(len(subsequence) + 1):
                for l in range(len(subsequence) + 1):
                    for m in range(len(subsequence) + 1):
                        for n in range(len(subsequence) + 1):
                            modified_subsequence = list(subsequence)
                            number_of_changes = 0

                            if j < len(subsequence) and number_of_changes < max_changes:
                                modified_subsequence[j] = 'a' if modified_subsequence[j] != 'a' else 'b'
                                number_of_changes += 1
                            if k < len(subsequence) and number_of_changes < max_changes:
                                modified_subsequence[k] = 'c' if modified_subsequence[k] != 'c' else 'a'
                                number_of_changes += 1
                            if l < len(subsequence) and number_of_changes < max_changes:
                                modified_subsequence[l] = 'b' if modified_subsequence[l] != 'b' else 'c'
                                number_of_changes += 1
                            if m < len(subsequence) and number_of_changes < max_changes:
                                modified_subsequence[m] = 'a' if modified_subsequence[m] != 'a' else 'c'
                                number_of_changes += 1
                            if n < len(subsequence) and number_of_changes < max_changes:
                                modified_subsequence[n] = 'b' if modified_subsequence[n] != 'b' else 'a'
                                number_of_changes += 1

                            modified_subsequence = "".join(modified_subsequence)

                            # Only consider the subsequence if it's a palindrome
                            if modified_subsequence == modified_subsequence[::-1]:

                                # Update the longest palindrome found so far
                                if len(modified_subsequence) > len(longest_palindrome):
                                    longest_palindrome = modified_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 about palindromes: A palindrome reads the same forward and backward. We want to find the longest one that we can make from the given sequence.
Consider the ends of the sequence: If the characters at the start and end of the sequence are the same, they can both be part of the palindromic subsequence.
If the characters are different, we need to use an operation to make them the same or skip either the beginning or the end of the sequence. Because we can perform a limited number of operations, we will check how many operations we will use in our solution.
Use a table to store results: Build a table where each cell represents the longest palindromic subsequence for a specific part of the sequence. The table stores the length of the palindromic subsequence and the number of operations used to build the subsequence.
Fill the table diagonally: Start filling the table from the shortest subsequences to the longest ones. For each subsequence, check if the ends match. If they do, add 2 to the length of the inner subsequence's palindrome. If they don't match, consider changing one end to match the other and increment the operations used.
Choose the best option: For each subsequence, check all the possible answers using the values already calculated and pick the one that gives you the longest palindromic subsequence using at most the maximum number of operations allowed. When the ends don't match, compare the lengths when skipping either beginning or ending.
The final answer: The value in the table cell that represents the entire sequence will contain the length of the longest palindromic subsequence that can be created with at most K operations.

Code Implementation

def longest_palindrome_subsequence_after_k_operations(sequence, max_operations):
    sequence_length = len(sequence)
    
    # Initialize DP table: dp[i][j] = (length, operations)
    dp_table = [[(0, 0) for _ in range(sequence_length)] for _ in range(sequence_length)]

    # Base case: single characters are palindromes with 0 operations
    for i in range(sequence_length):
        dp_table[i][i] = (1, 0)

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

            # If the ends match, extend the inner palindrome
            if sequence[i] == sequence[j]:
                dp_table[i][j] = (dp_table[i+1][j-1][0] + 2, dp_table[i+1][j-1][1])

            # If they don't match, consider changing characters or skipping
            else:
                length_without_beginning,
                operations_without_beginning = dp_table[i+1][j]
                
                length_without_ending,
                operations_without_ending = dp_table[i][j-1]

                # Determine which choice creates
                # the longer palindromic subsequence
                if length_without_beginning > length_without_ending:
                    longest_subsequence_length = length_without_beginning
                    operations_needed = operations_without_beginning
                else:
                    longest_subsequence_length = length_without_ending
                    operations_needed = operations_without_ending
                    
                # Check if using an operation to match
                # chars results in a longer subsequence
                length_with_operation,
                operations_with_operation = dp_table[i+1][j-1]
                
                if operations_with_operation < max_operations and \
                   length_with_operation + 2 > longest_subsequence_length :
                        longest_subsequence_length = length_with_operation + 2
                        operations_needed = operations_with_operation + 1

                #Store the result in the DP table
                dp_table[i][j] = (longest_subsequence_length, operations_needed)

    #The top-right cell contains the result
    return dp_table[0][sequence_length-1][0]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return 0, as the longest palindromic subsequence has length 0.
String of length 1	Return 1, as a single character is a palindrome of length 1.
String of length 2	If the characters are equal, return 2; otherwise, if k > 0 return 2, else return 1.
String with all identical characters and K=0	Return the length of the string directly, as it is already a palindrome.
String with all identical characters and K > 0	Return the length of the string directly, as it is already a palindrome.
K is greater or equal to the length of the string	Return the length of the string, since we can make all characters equal.
Large input string and large K, potential for integer overflow during calculations	Use appropriate data types (e.g., long long) for storing intermediate results to prevent overflow.
String with no palindromic subsequence without operations and K=0	The length of longest palindromic subsequence is still calculated correctly based on matching pairs or single character selections if the string is not a palindrome and k=0

Null or empty string input

How to Handle:

Return 0, as the longest palindromic subsequence has length 0.

String of length 1

How to Handle:

Return 1, as a single character is a palindrome of length 1.

String of length 2

How to Handle:

If the characters are equal, return 2; otherwise, if k > 0 return 2, else return 1.

String with all identical characters and K=0

How to Handle:

Return the length of the string directly, as it is already a palindrome.

String with all identical characters and K > 0

How to Handle:

Return the length of the string directly, as it is already a palindrome.

K is greater or equal to the length of the string

How to Handle:

Return the length of the string, since we can make all characters equal.

Large input string and large K, potential for integer overflow during calculations

How to Handle:

Use appropriate data types (e.g., long long) for storing intermediate results to prevent overflow.

String with no palindromic subsequence without operations and K=0

How to Handle:

The length of longest palindromic subsequence is still calculated correctly based on matching pairs or single character selections if the string is not a palindrome and k=0