Jobs

Interviews

Discussions

Shortest Palindrome

Hard

Asked by:

More companies

13 views

Topics:

Strings

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

0 <= s.length <= 5 * 10⁴
s consists of lowercase English letters only.

Try coding it in LeetCode

Shortest Palindrome

Hard

Asked by:

13 views

Topics:

Strings

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

0 <= s.length <= 5 * 10⁴
s consists of lowercase English letters only.

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?
If there are multiple shortest palindromes that can be formed, is any one acceptable?
Is the input string case-sensitive? For example, should 'Racecar' be considered a palindrome?
By 'shortest palindrome,' do you mean the palindrome that is created by adding the fewest characters to the *beginning* of the input string `s`?

Brute Force Solution

Approach

The brute force way to find the shortest palindrome involves testing every possible prefix to add to the beginning of the original string. We keep checking until we find a combination that results in a palindrome.

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

Start by adding a single character to the beginning of the original string.
Check if the new string is a palindrome (reads the same backward as forward).
If it is, we've found a potential solution; save it.
If it's not, try adding the first two characters from the end of the original string to the beginning.
Check if this new string is a palindrome and save it if it is.
Continue this process, adding more characters from the end of the original string to the beginning, one at a time, and checking for palindromes each time.
Once we've tried all possible additions, find the shortest palindrome we saved.

Code Implementation

def shortest_palindrome_brute_force(original_string):
    shortest_palindrome = None

    for i in range(len(original_string)):
        prefix_to_add = original_string[:i][::-1]
        new_string = prefix_to_add + original_string

        # Need to check if the new string is a palindrome.
        if new_string == new_string[::-1]:

            # Update shortest_palindrome if it's shorter or non-existent
            if shortest_palindrome is None or len(new_string) < len(shortest_palindrome):
                shortest_palindrome = new_string

    # This handles the case where the original string is already a palindrome
    if original_string == original_string[::-1] and (shortest_palindrome is None or len(original_string) < len(shortest_palindrome)):
        shortest_palindrome = original_string

    if shortest_palindrome is None:
        return ""
    return shortest_palindrome

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates up to n times, adding prefixes of increasing length to the beginning of the input string. In each iteration, it checks if the newly formed string is a palindrome. Checking for a palindrome takes O(n) time because we are comparing the string to its reverse. Since we repeat the palindrome check operation up to n times, the overall time complexity is O(n * n * n), which simplifies to O(n³).

Space Complexity

O(N) – The provided brute force algorithm constructs new strings in each iteration to check for palindromes. In the worst-case scenario, where a palindrome is only found after adding almost all characters from the end of the original string to the beginning, the longest of these new strings can be of size almost 2N (N for the original string and almost N for the prefix). Since we save potential solutions, the longest saved string will take up space proportional to N, where N is the length of the original input string. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The goal is to find the shortest way to make a string a palindrome by adding characters to its beginning. The best approach cleverly reuses existing information about palindromes to avoid redundant checks. We identify the longest palindrome starting from the beginning of the string, and then add the reversed remaining part to the front.

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

Imagine drawing a line down the middle of the string and checking if the first part is a palindrome (reads the same backward as forward).
Start by checking if the entire string is already a palindrome. If so, you're done; no additions needed.
If the entire string isn't a palindrome, shorten the part you're checking from the end, little by little. At each step, check if the piece starting from the very beginning of the string and ending somewhere in the middle is a palindrome.
Keep shortening that piece until you find the longest possible palindrome that starts right at the beginning of the original string.
Once you've found that longest initial palindrome, take the part of the original string that's *not* part of this palindrome.
Reverse that remaining part of the string.
Add the reversed remaining part to the front of the original string. This guarantees the shortest palindrome you can create.

Code Implementation

def shortest_palindrome(input_string):
    string_length = len(input_string)
    for i in range(string_length, 0, -1):
        # Check for longest palindrome from start
        if input_string[:i] == input_string[:i][::-1]:

            longest_palindrome_prefix_length = i
            break

    remaining_string = input_string[longest_palindrome_prefix_length:]
    reversed_remaining_string = remaining_string[::-1]

    # Prepend reversed string for shortest palindrome
    shortest_palindromic_string = reversed_remaining_string + input_string

    return shortest_palindromic_string

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates, in the worst case, through decreasing prefixes of the input string s of length n, checking for palindromes. For each prefix, it performs a palindrome check which involves comparing characters from the beginning and end towards the middle, taking O(n) time in the worst case. Since the prefixes decrease in size from n down to 1, the total time complexity is approximately n + (n-1) + (n-2) + ... + 1 palindrome checks each taking O(n) time, which equals n * (n*(n+1)/2). This simplifies to O(n²).

Space Complexity

O(N) – The algorithm calculates the longest palindrome starting from the beginning, requiring the storage of the reversed remaining part of the string. This reversed string has a maximum length of N-1, where N is the length of the input string. Therefore, the space used for this temporary string scales linearly with the input size. This auxiliary space contributes O(N) to the overall space complexity.

Edge Cases

Case	How to Handle
Null or empty string input	Return an empty string immediately as there's nothing to make a palindrome from.
Single-character string input	Return the original string since a single character is already a palindrome.
String that is already a palindrome	Return the original string as no modifications are needed.
Long string with a very short non-palindromic prefix	Ensure the algorithm efficiently identifies and reverses only the minimum required prefix.
String with a long palindromic suffix but non-palindromic prefix	The algorithm should correctly identify the longest palindromic suffix, and prepend the reverse of the prefix before it.
String containing special characters or non-alphanumeric characters	The algorithm should treat these characters as regular characters or specify the valid range of characters.
String with a large number of repeated characters that are not palindromic	The algorithm needs to efficiently handle potentially large intermediate strings generated during the reversing and concatenation process.
Maximum string length exceeding memory capacity, leading to potential memory overflow	Consider using a rolling hash based approach or limiting the string length processed to prevent memory issues.

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?
If there are multiple shortest palindromes that can be formed, is any one acceptable?
Is the input string case-sensitive? For example, should 'Racecar' be considered a palindrome?
By 'shortest palindrome,' do you mean the palindrome that is created by adding the fewest characters to the *beginning* of the input string `s`?

Brute Force Solution

Approach

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

Start by adding a single character to the beginning of the original string.
Check if the new string is a palindrome (reads the same backward as forward).
If it is, we've found a potential solution; save it.
If it's not, try adding the first two characters from the end of the original string to the beginning.
Check if this new string is a palindrome and save it if it is.
Continue this process, adding more characters from the end of the original string to the beginning, one at a time, and checking for palindromes each time.
Once we've tried all possible additions, find the shortest palindrome we saved.

Code Implementation

def shortest_palindrome_brute_force(original_string):
    shortest_palindrome = None

    for i in range(len(original_string)):
        prefix_to_add = original_string[:i][::-1]
        new_string = prefix_to_add + original_string

        # Need to check if the new string is a palindrome.
        if new_string == new_string[::-1]:

            # Update shortest_palindrome if it's shorter or non-existent
            if shortest_palindrome is None or len(new_string) < len(shortest_palindrome):
                shortest_palindrome = new_string

    # This handles the case where the original string is already a palindrome
    if original_string == original_string[::-1] and (shortest_palindrome is None or len(original_string) < len(shortest_palindrome)):
        shortest_palindrome = original_string

    if shortest_palindrome is None:
        return ""
    return shortest_palindrome

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine drawing a line down the middle of the string and checking if the first part is a palindrome (reads the same backward as forward).
Start by checking if the entire string is already a palindrome. If so, you're done; no additions needed.
If the entire string isn't a palindrome, shorten the part you're checking from the end, little by little. At each step, check if the piece starting from the very beginning of the string and ending somewhere in the middle is a palindrome.
Keep shortening that piece until you find the longest possible palindrome that starts right at the beginning of the original string.
Once you've found that longest initial palindrome, take the part of the original string that's *not* part of this palindrome.
Reverse that remaining part of the string.
Add the reversed remaining part to the front of the original string. This guarantees the shortest palindrome you can create.

Code Implementation

def shortest_palindrome(input_string):
    string_length = len(input_string)
    for i in range(string_length, 0, -1):
        # Check for longest palindrome from start
        if input_string[:i] == input_string[:i][::-1]:

            longest_palindrome_prefix_length = i
            break

    remaining_string = input_string[longest_palindrome_prefix_length:]
    reversed_remaining_string = remaining_string[::-1]

    # Prepend reversed string for shortest palindrome
    shortest_palindromic_string = reversed_remaining_string + input_string

    return shortest_palindromic_string

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return an empty string immediately as there's nothing to make a palindrome from.
Single-character string input	Return the original string since a single character is already a palindrome.
String that is already a palindrome	Return the original string as no modifications are needed.
Long string with a very short non-palindromic prefix	Ensure the algorithm efficiently identifies and reverses only the minimum required prefix.
String with a long palindromic suffix but non-palindromic prefix	The algorithm should correctly identify the longest palindromic suffix, and prepend the reverse of the prefix before it.
String containing special characters or non-alphanumeric characters	The algorithm should treat these characters as regular characters or specify the valid range of characters.
String with a large number of repeated characters that are not palindromic	The algorithm needs to efficiently handle potentially large intermediate strings generated during the reversing and concatenation process.
Maximum string length exceeding memory capacity, leading to potential memory overflow	Consider using a rolling hash based approach or limiting the string length processed to prevent memory issues.