Jobs

Interviews

Discussions

Longest Palindromic Substring

Medium

Disney

0 views

Topics:

StringsDynamic ProgrammingTwo Pointers

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

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

Longest Palindromic Substring

Medium

Disney

0 views

Topics:

StringsDynamic ProgrammingTwo Pointers

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

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

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 palindromic substrings of the same maximum length, which one should I return?
Is the input string `s` case-sensitive? For example, should "Racecar" be considered a palindrome?
Are there any special characters or non-ASCII characters in the input string `s`?

Brute Force Solution

Approach

The brute force method finds the longest palindrome by checking every possible piece of the input. It's like trying every possible answer until you find the right one. We will go through each possible substring and check if it's a palindrome.

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

First, consider every single letter in the input as a possible palindrome.
Next, look at every pair of letters next to each other, then every group of three letters, then four, and so on, until you've considered the entire input as one big string.
For each of these groups of letters, check if it reads the same forwards and backward. If it does, it's a palindrome.
Keep track of the longest palindrome you find during this process.
Once you have checked every possible group of letters, the longest palindrome you found is your answer.

Code Implementation

def longest_palindromic_substring_brute_force(input_string):
    longest_palindrome = ""
    input_length = len(input_string)

    # Iterate through all possible starting positions
    for starting_index in range(input_length):
        # Iterate through all possible ending positions
        for ending_index in range(starting_index, input_length):
            substring = input_string[starting_index:ending_index + 1]

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

                # Update longest palindrome if current substring is longer
                if len(substring) > len(longest_palindrome):
                    longest_palindrome = substring

    return longest_palindrome

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through all possible substrings of the input string of length n. Generating all possible substrings requires two nested loops, resulting in O(n^2) substrings. For each substring, the algorithm checks if it's a palindrome, which takes O(n) time in the worst case (checking each character of the substring). Therefore, the overall time complexity is O(n^2 * n), which simplifies to O(n^3).

Space Complexity

O(1) – The brute force method described only requires a constant amount of extra space. Specifically, it needs to store the longest palindrome found so far, which can be represented by a start index and length (or the substring itself in some implementations). The space used for these variables doesn't depend on the input string's length (N), remaining constant regardless of how large the input string is. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The best way to find the longest palindrome inside a string is to think about it growing outward from the middle. We check every possible center of a palindrome and expand to see how big it can get.

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

Consider each position in the string as a potential center of a palindrome.
For each center, try to expand to the left and right to check for palindromes. There are two cases to consider: a palindrome of odd length (centered on one character) and a palindrome of even length (centered between two characters).
Keep track of the longest palindrome found so far.
Compare the length of any new palindromes found to the longest one.
At the end, the longest palindrome tracked is the answer.

Code Implementation

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

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

        # Expand around center, i.
        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 the longest palindrome if needed.
            if len(current_palindrome) > len(longest_palindrome):
                longest_palindrome = current_palindrome

            left_index -= 1
            right_index += 1

        # Check for even length palindromes.
        left_index = i
        right_index = i + 1

        # This loop expands around a potential center, i & i+1.
        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 the longest palindrome if needed.
            if len(current_palindrome) > len(longest_palindrome):
                longest_palindrome = current_palindrome

            left_index -= 1
            right_index += 1

    return longest_palindrome

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each character in the string of length n, considering it as a potential center for a palindrome. For each center, it expands outwards, in the worst case, potentially checking all characters to the left and right. This expansion process takes O(n) time for each center. Since there are n possible centers and each expansion can take up to O(n) time, the overall time complexity is O(n * n) which simplifies to O(n²).

Space Complexity

O(1) – The algorithm described iterates through the string, potentially updating the start and end indices of the longest palindrome found so far. It does not create any auxiliary data structures whose size depends on the input string length N. Therefore, the space required is constant, resulting in a space complexity of O(1).

Edge Cases

Case	How to Handle
Null or empty string input	Return an empty string or handle as an error, depending on requirements specification.
String with a single character	Return the single character string itself since it's a palindrome.
String with two identical characters (e.g., 'aa')	Return the entire string as it's a palindrome.
String with two different characters (e.g., 'ab')	Return either 'a' or 'b', as they are the longest palindromic substrings of length 1.
String with all identical characters (e.g., 'aaaa')	Return the entire string since it's a palindrome.
Very long string to test for performance	Ensure the algorithm has at least O(n^2) or better time complexity to avoid timeouts.
String with many overlapping palindromes	Algorithm needs to correctly identify and select the longest among possibly many overlapping palindromes.
String with no palindromic substring longer than 1 character	Return any single character substring, since the problem guarantees at least one exists.

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 palindromic substrings of the same maximum length, which one should I return?
Is the input string `s` case-sensitive? For example, should "Racecar" be considered a palindrome?
Are there any special characters or non-ASCII characters in the input string `s`?

Brute Force Solution

Approach

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

First, consider every single letter in the input as a possible palindrome.
Next, look at every pair of letters next to each other, then every group of three letters, then four, and so on, until you've considered the entire input as one big string.
For each of these groups of letters, check if it reads the same forwards and backward. If it does, it's a palindrome.
Keep track of the longest palindrome you find during this process.
Once you have checked every possible group of letters, the longest palindrome you found is your answer.

Code Implementation

def longest_palindromic_substring_brute_force(input_string):
    longest_palindrome = ""
    input_length = len(input_string)

    # Iterate through all possible starting positions
    for starting_index in range(input_length):
        # Iterate through all possible ending positions
        for ending_index in range(starting_index, input_length):
            substring = input_string[starting_index:ending_index + 1]

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

                # Update longest palindrome if current substring is longer
                if len(substring) > len(longest_palindrome):
                    longest_palindrome = substring

    return longest_palindrome

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The best way to find the longest palindrome inside a string is to think about it growing outward from the middle. We check every possible center of a palindrome and expand to see how big it can get.

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

Consider each position in the string as a potential center of a palindrome.
For each center, try to expand to the left and right to check for palindromes. There are two cases to consider: a palindrome of odd length (centered on one character) and a palindrome of even length (centered between two characters).
Keep track of the longest palindrome found so far.
Compare the length of any new palindromes found to the longest one.
At the end, the longest palindrome tracked is the answer.

Code Implementation

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

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

        # Expand around center, i.
        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 the longest palindrome if needed.
            if len(current_palindrome) > len(longest_palindrome):
                longest_palindrome = current_palindrome

            left_index -= 1
            right_index += 1

        # Check for even length palindromes.
        left_index = i
        right_index = i + 1

        # This loop expands around a potential center, i & i+1.
        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 the longest palindrome if needed.
            if len(current_palindrome) > len(longest_palindrome):
                longest_palindrome = current_palindrome

            left_index -= 1
            right_index += 1

    return longest_palindrome

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return an empty string or handle as an error, depending on requirements specification.
String with a single character	Return the single character string itself since it's a palindrome.
String with two identical characters (e.g., 'aa')	Return the entire string as it's a palindrome.
String with two different characters (e.g., 'ab')	Return either 'a' or 'b', as they are the longest palindromic substrings of length 1.
String with all identical characters (e.g., 'aaaa')	Return the entire string since it's a palindrome.
Very long string to test for performance	Ensure the algorithm has at least O(n^2) or better time complexity to avoid timeouts.
String with many overlapping palindromes	Algorithm needs to correctly identify and select the longest among possibly many overlapping palindromes.
String with no palindromic substring longer than 1 character	Return any single character substring, since the problem guarantees at least one exists.