Jobs

Interviews

Discussions

Valid Palindrome III

Hard

TikTok

0 views

Topics:

StringsDynamic Programming

Given a string s and an integer k, find out if the given string is a K-Palindrome or not.

A string is K-Palindrome if it can be transformed into a palindrome by removing at most k characters from it.

Example 1:

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

Example 2:

Input: s = "abbababa", k = 1
Output: true

Constraints:

1 <= s.length <= 1000
s has only lowercase English letters.
1 <= k <= s.length

Valid Palindrome III

Hard

TikTok

0 views

Topics:

StringsDynamic Programming

Given a string s and an integer k, find out if the given string is a K-Palindrome or not.

A string is K-Palindrome if it can be transformed into a palindrome by removing at most k characters from it.

Example 1:

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

Example 2:

Input: s = "abbababa", k = 1
Output: true

Constraints:

1 <= s.length <= 1000
s has only lowercase English letters.
1 <= k <= s.length

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` and the maximum value for `k`?
Can the input string `s` contain characters other than lowercase English letters?
If the input string is empty, what should be the return value?
If the string `s` is already a palindrome, what should be the return value?
If `k` is 0, is the string `s` required to be a perfect palindrome (no removals allowed)?

Brute Force Solution

Approach

The brute force approach to checking if a string can become a palindrome within a certain number of deletions involves trying all possible combinations of character deletions. We generate every possible modified string by removing different sets of characters. Then, for each modified string, we simply check if it's a palindrome and whether we removed no more than the allowed number of characters.

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

First, consider removing no characters at all from the original string. Check if the original string is a palindrome.
Next, try removing one character at a time from every possible position in the string. For each of these new strings, check if it is a palindrome.
Then, try removing two characters at a time from every possible combination of positions in the original string. Check each of these new strings to see if they are palindromes.
Keep doing this, removing three characters, four characters, and so on, up to the maximum number of allowed removals.
Each time we create a new string by removing characters, check if it is a palindrome. If we find a palindrome string and the number of removed characters is within the limit, then we know the original string can become a palindrome with that many deletions.
If, after checking all possibilities of removing characters, we haven't found a palindrome string that meets the deletion limit, then the original string cannot become a palindrome within the given constraints.

Code Implementation

def is_valid_palindrome_iii_brute_force(input_string, allowed_deletions):
    string_length = len(input_string)

    # Helper function to check if a string is a palindrome
    def is_palindrome(some_string):
        return some_string == some_string[::-1]

    # Check the original string with no deletions
    if is_palindrome(input_string):
        return True

    # Iterate through all possible deletion counts
    for number_of_deletions in range(1, allowed_deletions + 1):
        # Generate all combinations of indices to delete
        def generate_combinations(current_combination, start_index, count):
            if count == 0:
                modified_string = ""
                original_index = 0
                deletion_index = 0
                while original_index < string_length:
                    if deletion_index < len(current_combination) and original_index == current_combination[deletion_index]:
                        original_index += 1
                        deletion_index += 1
                    else:
                        modified_string += input_string[original_index]
                        original_index += 1

                # Check if the modified string is a palindrome
                if is_palindrome(modified_string):
                    return True
                else:
                    return False

            for i in range(start_index, string_length):
                if generate_combinations(current_combination + [i], i + 1, count - 1):
                    return True
            return False

        # Try all combinations of deletions for current number of deletions
        if generate_combinations([], 0, number_of_deletions):
            return True

    # No palindrome found within the allowed deletions
    return False

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible subsets of characters to remove from the string. For a string of length n, there are 2^n possible subsets (each character can either be included or excluded). For each subset, it checks if the resulting string is a palindrome, which takes O(n) time. However, the dominant factor is the generation of all subsets. Therefore, the overall time complexity is O(2^n * n), which is simplified to O(2^n) because the exponential term dominates.

Space Complexity

O(2^N) – The brute force approach generates all possible substrings by removing characters. In the worst-case scenario, where N is the length of the input string, we consider all possible subsets of characters to remove. Generating all subsets results in 2^N possible modified strings. While we don't explicitly store all 2^N strings simultaneously, the recursive calls or iterative approach used to explore the possibilities can lead to a space complexity that is proportional to the number of possible subsets generated, especially if intermediate strings are stored during the process, leading to an exponential space complexity.

Optimal Solution

Approach

To check if a string can become a palindrome with a limited number of changes, we use a dynamic programming approach. We essentially find the longest palindromic subsequence within the string and see if removing the non-palindrome characters exceeds our allowed change limit.

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

Imagine a table where each cell represents a substring of the original string.
Fill the table diagonally, starting with single characters and then progressively larger substrings.
For each substring, check if its first and last characters are the same.
If they are the same, the longest palindromic subsequence is two more than the longest palindromic subsequence of the inner substring (excluding the first and last characters).
If they are different, the longest palindromic subsequence is the larger of the longest palindromic subsequences obtained by removing either the first or last character.
Once the entire table is filled, the value in the cell representing the original string indicates the length of the longest palindromic subsequence.
Subtract the length of the longest palindromic subsequence from the length of the original string to determine how many characters need to be changed or removed to make it a palindrome.
Finally, compare the number of changes needed with the allowed number of changes; if the needed changes are less than or equal to the allowed changes, the string can become a palindrome.

Code Implementation

def is_valid_palindrome_iii(text_string, allowed_changes):
    string_length = len(text_string)
    
    # DP table to store lengths of longest palindromic subsequences.
    dp_table = [[0] * string_length for _ in range(string_length)]

    for i in range(string_length):
        dp_table[i][i] = 1

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

            # Check if the characters at the ends match.
            if text_string[i] == text_string[j]:

                # If they match, extend the palindromic subsequence.
                if substring_length == 2:
                    dp_table[i][j] = 2
                else:
                    dp_table[i][j] = dp_table[i+1][j-1] + 2
            else:
                # If they don't, take the max of excluding either end.
                dp_table[i][j] = max(dp_table[i+1][j], dp_table[i][j-1])

    # Calculate the number of changes needed.
    changes_needed = string_length - dp_table[0][string_length-1]

    # Compare needed changes with allowed changes.
    return changes_needed <= allowed_changes

Big(O) Analysis

Time Complexity

O(n²) – The dynamic programming approach involves filling an n x n table, where n is the length of the input string. Each cell in the table represents a substring and requires constant time to compute the longest palindromic subsequence length based on previously computed values. Therefore, the time complexity is determined by the number of cells in the table, which is n * n. Thus, the overall time complexity is O(n²).

Space Complexity

O(N^2) – The dynamic programming approach uses a table (or 2D array) to store the lengths of the longest palindromic subsequences for all possible substrings. This table has dimensions N x N, where N is the length of the input string. Therefore, the auxiliary space required to store this table is proportional to N^2, resulting in a space complexity of O(N^2).

Edge Cases

Case	How to Handle
Null or empty string input	Return true immediately as an empty string can be considered a palindrome with zero deletions.
String with length 1	Return true immediately as a single-character string is always a palindrome.
String with length 2 and k=0 and chars don't match	Return false since we can't make it a palindrome without deletions.
String with length 2 and k=0 and chars do match	Return true immediately.
String with all same characters and k = 0	Return true as it's already a palindrome.
String with all same characters and k > 0	Return true as it's already a palindrome.
k is greater than or equal to the length of the string divided by 2	Return true immediately as we can delete enough characters to make it a palindrome (potentially empty).
Maximum string length approaching memory limits.	Ensure dynamic programming table (if used) doesn't exceed available memory; consider iterative solution to reduce stack usage.

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` and the maximum value for `k`?
Can the input string `s` contain characters other than lowercase English letters?
If the input string is empty, what should be the return value?
If the string `s` is already a palindrome, what should be the return value?
If `k` is 0, is the string `s` required to be a perfect palindrome (no removals allowed)?

Brute Force Solution

Approach

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

First, consider removing no characters at all from the original string. Check if the original string is a palindrome.
Next, try removing one character at a time from every possible position in the string. For each of these new strings, check if it is a palindrome.
Then, try removing two characters at a time from every possible combination of positions in the original string. Check each of these new strings to see if they are palindromes.
Keep doing this, removing three characters, four characters, and so on, up to the maximum number of allowed removals.
Each time we create a new string by removing characters, check if it is a palindrome. If we find a palindrome string and the number of removed characters is within the limit, then we know the original string can become a palindrome with that many deletions.
If, after checking all possibilities of removing characters, we haven't found a palindrome string that meets the deletion limit, then the original string cannot become a palindrome within the given constraints.

Code Implementation

def is_valid_palindrome_iii_brute_force(input_string, allowed_deletions):
    string_length = len(input_string)

    # Helper function to check if a string is a palindrome
    def is_palindrome(some_string):
        return some_string == some_string[::-1]

    # Check the original string with no deletions
    if is_palindrome(input_string):
        return True

    # Iterate through all possible deletion counts
    for number_of_deletions in range(1, allowed_deletions + 1):
        # Generate all combinations of indices to delete
        def generate_combinations(current_combination, start_index, count):
            if count == 0:
                modified_string = ""
                original_index = 0
                deletion_index = 0
                while original_index < string_length:
                    if deletion_index < len(current_combination) and original_index == current_combination[deletion_index]:
                        original_index += 1
                        deletion_index += 1
                    else:
                        modified_string += input_string[original_index]
                        original_index += 1

                # Check if the modified string is a palindrome
                if is_palindrome(modified_string):
                    return True
                else:
                    return False

            for i in range(start_index, string_length):
                if generate_combinations(current_combination + [i], i + 1, count - 1):
                    return True
            return False

        # Try all combinations of deletions for current number of deletions
        if generate_combinations([], 0, number_of_deletions):
            return True

    # No palindrome found within the allowed deletions
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine a table where each cell represents a substring of the original string.
Fill the table diagonally, starting with single characters and then progressively larger substrings.
For each substring, check if its first and last characters are the same.
If they are the same, the longest palindromic subsequence is two more than the longest palindromic subsequence of the inner substring (excluding the first and last characters).
If they are different, the longest palindromic subsequence is the larger of the longest palindromic subsequences obtained by removing either the first or last character.
Once the entire table is filled, the value in the cell representing the original string indicates the length of the longest palindromic subsequence.
Subtract the length of the longest palindromic subsequence from the length of the original string to determine how many characters need to be changed or removed to make it a palindrome.
Finally, compare the number of changes needed with the allowed number of changes; if the needed changes are less than or equal to the allowed changes, the string can become a palindrome.

Code Implementation

def is_valid_palindrome_iii(text_string, allowed_changes):
    string_length = len(text_string)
    
    # DP table to store lengths of longest palindromic subsequences.
    dp_table = [[0] * string_length for _ in range(string_length)]

    for i in range(string_length):
        dp_table[i][i] = 1

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

            # Check if the characters at the ends match.
            if text_string[i] == text_string[j]:

                # If they match, extend the palindromic subsequence.
                if substring_length == 2:
                    dp_table[i][j] = 2
                else:
                    dp_table[i][j] = dp_table[i+1][j-1] + 2
            else:
                # If they don't, take the max of excluding either end.
                dp_table[i][j] = max(dp_table[i+1][j], dp_table[i][j-1])

    # Calculate the number of changes needed.
    changes_needed = string_length - dp_table[0][string_length-1]

    # Compare needed changes with allowed changes.
    return changes_needed <= allowed_changes

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return true immediately as an empty string can be considered a palindrome with zero deletions.
String with length 1	Return true immediately as a single-character string is always a palindrome.
String with length 2 and k=0 and chars don't match	Return false since we can't make it a palindrome without deletions.
String with length 2 and k=0 and chars do match	Return true immediately.
String with all same characters and k = 0	Return true as it's already a palindrome.
String with all same characters and k > 0	Return true as it's already a palindrome.
k is greater than or equal to the length of the string divided by 2	Return true immediately as we can delete enough characters to make it a palindrome (potentially empty).
Maximum string length approaching memory limits.	Ensure dynamic programming table (if used) doesn't exceed available memory; consider iterative solution to reduce stack usage.