Jobs

Interviews

Discussions

Longest Palindromic Substring

Medium

Uber

0 views

Topics:

StringsDynamic Programming

Given a string s, return the longest palindromic substring in s.

For example:

If s = "babad", the output should be "bab" or "aba" because both are valid palindromic substrings and have the longest length.
If s = "cbbd", the output should be "bb".

Clarifications:

What should be returned if the input string s is empty?
Can I assume that the input string s consists only of digits and English letters?
What is the expected time and space complexity?

Longest Palindromic Substring

Medium

Uber

0 views

Topics:

StringsDynamic Programming

Given a string s, return the longest palindromic substring in s.

For example:

If s = "babad", the output should be "bab" or "aba" because both are valid palindromic substrings and have the longest length.
If s = "cbbd", the output should be "bb".

Clarifications:

What should be returned if the input string s is empty?
Can I assume that the input string s consists only of digits and English letters?
What is the expected time and space complexity?

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:

Can the input string `s` be empty or null?
If there are multiple longest palindromic substrings of the same length, should I return any one of them or is there a specific one I should prioritize (e.g., the one that appears first)?
Is the string `s` case-sensitive? For example, should 'Racecar' be considered a palindrome?
Are there any constraints on the characters that can appear in the string `s` (e.g., only alphanumeric characters, or can it contain special characters)?
Is a single character a valid palindrome, and should I return the single character if the string contains no palindromes of length 2 or greater?

Brute Force Solution

Approach

The brute force method for finding the longest palindromic section within a piece of text is like checking every single possible section. We consider every starting point and every possible ending point to identify sections. Then, we simply determine if each section we discover is actually a palindrome.

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

Begin by selecting a starting location in the text.
From that starting location, consider every possible ending location within the text.
Each time you define a section using a starting and ending location, check if that specific section reads the same forwards and backwards (that's how you know if it's a palindrome).
Keep track of all the sections you found that are palindromes.
After checking every possible section, find the longest palindrome among all the palindromes you identified.

Code Implementation

def longest_palindrome_brute_force(input_string):
    longest_palindrome = ""

    for starting_index in range(len(input_string)):
        for ending_index in range(starting_index, len(input_string)):

            substring = input_string[starting_index:ending_index + 1]

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

                #Keep track of the longest palindrome found
                if len(substring) > len(longest_palindrome):
                    longest_palindrome = substring

    return longest_palindrome

Big(O) Analysis

Time Complexity

O(n^3) – The described brute force approach involves three key operations that contribute to its time complexity. First, there are two nested loops to generate all possible substrings of the input string of length n. The outer loop iterates n times to select a starting position. The inner loop iterates up to n times to select an ending position from the chosen start. Thus, the pair generation is O(n^2). The most important complexity driver is that for each substring, a palindrome check is performed, which takes O(n) time in the worst case (comparing characters from the start and end towards the middle of the string). Therefore, the overall time complexity is O(n^2 * n) = O(n^3).

Space Complexity

O(1) – The brute force approach described iterates through all possible substrings using nested loops but it only stores the longest palindromic substring found so far. It doesn't create any auxiliary data structures of significant size related to the input text's length. Therefore, the space complexity is constant, regardless of the input string's length N because we are only storing a few variables like start index, end index, and maximum length encountered so far.

Optimal Solution

Approach

The best way to find the longest palindrome involves strategically expanding around each possible center. We efficiently check for palindromes by growing outwards, skipping many unnecessary comparisons. This avoids the need to examine every single possible substring.

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

Imagine each character in the string as the potential center of a palindrome.
Consider each space between characters as another potential center of a palindrome (for even-length palindromes).
For each center (character or space), expand outwards, one character at a time, on both sides.
As you expand, check if the characters on the left and right are the same. If they are, the substring between them is a palindrome.
Keep expanding as long as the characters on both sides match. If they don't match, stop expanding for that center.
Keep track of the longest palindrome you've found so far.
After checking all possible centers and their expansions, the longest palindrome you tracked is the answer.

Code Implementation

def longest_palindromic_substring(input_string):
    string_length = len(input_string)
    longest_palindrome = ""

    for center_index in range(string_length):
        # Check for odd length palindromes.
        left_index = center_index
        right_index = center_index

        # Expand around the center.
        while left_index >= 0 and right_index < string_length and input_string[left_index] == input_string[right_index]:
            current_palindrome = input_string[left_index:right_index + 1]

            # Update longest palindrome if needed
            if len(current_palindrome) > len(longest_palindrome):
                longest_palindrome = current_palindrome

            left_index -= 1
            right_index += 1

    for center_index in range(string_length - 1):
        # Check for even length palindromes.
        left_index = center_index
        right_index = center_index + 1

        # Expand around the center
        while left_index >= 0 and right_index < string_length and input_string[left_index] == input_string[right_index]:
            # Extract the current palindrome.
            current_palindrome = input_string[left_index:right_index + 1]

            # Update longest palindrome if needed.
            if len(current_palindrome) > len(longest_palindrome):
                longest_palindrome = current_palindrome

            left_index -= 1
            right_index += 1

    return longest_palindrome

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each character of the string (length n) as a potential center of a palindrome. For each center, it expands outwards, potentially comparing characters on both sides until the boundaries of the string are reached. In the worst-case scenario (e.g., a string like 'aaaaa'), the expansion for each center could take up to n/2 comparisons. Therefore, the total number of operations is proportional to n * (n/2), which simplifies to O(n²).

Space Complexity

O(1) – The described algorithm primarily uses a few variables to keep track of the start and end indices of the longest palindrome found so far. The expansion process involves comparing characters within the input string and updating these indices. Since it does not use any auxiliary data structures like arrays, hashmaps, or recursion that scale with the input size N, the extra space required remains constant regardless of the length of the input string. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or handle the null case appropriately (e.g., throw an exception depending on requirements).
Single character input string	Return the single character string as it is trivially a palindrome.
Two character input string that is a palindrome	Return the entire two-character string.
Two character input string that is not a palindrome	Return either of the single characters, as they are both palindromes of length 1.
Input string with all identical characters	Return the entire string as it's a palindrome.
Maximum length string (1000 characters)	Ensure the chosen algorithm's time complexity is efficient enough to handle this size within reasonable time constraints (e.g., O(n^2) or better).
String with multiple palindromic substrings of the same maximum length	The algorithm should return only one of these substrings - the first one found is usually acceptable if the prompt does not explicitly ask for 'all' palindromes.
String with very long non-palindromic sequences and a short palindromic sequence	The algorithm should efficiently identify the palindromic sequence without excessive computation on the non-palindromic portions.

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:

Can the input string `s` be empty or null?
If there are multiple longest palindromic substrings of the same length, should I return any one of them or is there a specific one I should prioritize (e.g., the one that appears first)?
Is the string `s` case-sensitive? For example, should 'Racecar' be considered a palindrome?
Are there any constraints on the characters that can appear in the string `s` (e.g., only alphanumeric characters, or can it contain special characters)?
Is a single character a valid palindrome, and should I return the single character if the string contains no palindromes of length 2 or greater?

Brute Force Solution

Approach

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

Begin by selecting a starting location in the text.
From that starting location, consider every possible ending location within the text.
Each time you define a section using a starting and ending location, check if that specific section reads the same forwards and backwards (that's how you know if it's a palindrome).
Keep track of all the sections you found that are palindromes.
After checking every possible section, find the longest palindrome among all the palindromes you identified.

Code Implementation

def longest_palindrome_brute_force(input_string):
    longest_palindrome = ""

    for starting_index in range(len(input_string)):
        for ending_index in range(starting_index, len(input_string)):

            substring = input_string[starting_index:ending_index + 1]

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

                #Keep track of the longest palindrome found
                if len(substring) > len(longest_palindrome):
                    longest_palindrome = substring

    return longest_palindrome

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine each character in the string as the potential center of a palindrome.
Consider each space between characters as another potential center of a palindrome (for even-length palindromes).
For each center (character or space), expand outwards, one character at a time, on both sides.
As you expand, check if the characters on the left and right are the same. If they are, the substring between them is a palindrome.
Keep expanding as long as the characters on both sides match. If they don't match, stop expanding for that center.
Keep track of the longest palindrome you've found so far.
After checking all possible centers and their expansions, the longest palindrome you tracked is the answer.

Code Implementation

def longest_palindromic_substring(input_string):
    string_length = len(input_string)
    longest_palindrome = ""

    for center_index in range(string_length):
        # Check for odd length palindromes.
        left_index = center_index
        right_index = center_index

        # Expand around the center.
        while left_index >= 0 and right_index < string_length and input_string[left_index] == input_string[right_index]:
            current_palindrome = input_string[left_index:right_index + 1]

            # Update longest palindrome if needed
            if len(current_palindrome) > len(longest_palindrome):
                longest_palindrome = current_palindrome

            left_index -= 1
            right_index += 1

    for center_index in range(string_length - 1):
        # Check for even length palindromes.
        left_index = center_index
        right_index = center_index + 1

        # Expand around the center
        while left_index >= 0 and right_index < string_length and input_string[left_index] == input_string[right_index]:
            # Extract the current palindrome.
            current_palindrome = input_string[left_index:right_index + 1]

            # Update longest palindrome if needed.
            if len(current_palindrome) > len(longest_palindrome):
                longest_palindrome = current_palindrome

            left_index -= 1
            right_index += 1

    return longest_palindrome

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or handle the null case appropriately (e.g., throw an exception depending on requirements).
Single character input string	Return the single character string as it is trivially a palindrome.
Two character input string that is a palindrome	Return the entire two-character string.
Two character input string that is not a palindrome	Return either of the single characters, as they are both palindromes of length 1.
Input string with all identical characters	Return the entire string as it's a palindrome.
Maximum length string (1000 characters)	Ensure the chosen algorithm's time complexity is efficient enough to handle this size within reasonable time constraints (e.g., O(n^2) or better).
String with multiple palindromic substrings of the same maximum length	The algorithm should return only one of these substrings - the first one found is usually acceptable if the prompt does not explicitly ask for 'all' palindromes.
String with very long non-palindromic sequences and a short palindromic sequence	The algorithm should efficiently identify the palindromic sequence without excessive computation on the non-palindromic portions.