Jobs

Interviews

Discussions

Longest Palindromic Substring

#3 Most AskedMedium

Longest Palindromic Substring #3 Most Asked

Medium

Netskope

21 views

Topics:

StringsTwo PointersDynamic Programming

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.

Try coding it in LeetCode

Longest Palindromic Substring

#3 Most AskedMedium

Longest Palindromic Substring #3 Most Asked

Medium

Netskope

21 views

Topics:

StringsTwo PointersDynamic Programming

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.

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 `s`? Can it be empty, or very long?
Are there any restrictions on the characters that can be present in the string `s` (e.g., only lowercase English letters, uppercase, digits, special characters)?
If there are multiple palindromic substrings of the same maximum length, which one should I return (e.g., the first one encountered, the last one)?
Is it possible for the input string to be null or undefined?
Does the problem statement imply any specific character encoding or collation rules that might affect palindrome checks?

Brute Force Solution

Approach

The brute force approach to finding the longest palindromic substring involves checking every single possible substring within the given text. For each substring, we then determine if it reads the same forwards and backward.

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

Consider every possible starting point for a potential substring within the original text.
From each starting point, consider every possible ending point to form a substring.
For every substring you create, check if it is a palindrome. A palindrome is something that reads the same forwards and backward.
Keep track of all the substrings that you find to be palindromes.
After checking all possible substrings, select the longest one from the list of palindromes you've collected.

Code Implementation

def longest_palindromic_substring_brute_force(input_string):    longest_palindrome_found = ""    # We need to check every possible substring, so we iterate through all start and end points.    for starting_index in range(len(input_string)):        for ending_index in range(starting_index, len(input_string)):            current_substring = input_string[starting_index : ending_index + 1]            # A palindrome reads the same forwards and backwards.            if current_substring == current_substring[::-1]:                # We update our longest palindrome if the current one is longer.                if len(current_substring) > len(longest_palindrome_found):                    longest_palindrome_found = current_substring    return longest_palindrome_found

Big(O) Analysis

Time Complexity

O(n³) – The brute force approach iterates through all possible starting positions of a substring, which takes O(n) time. For each starting position, it iterates through all possible ending positions, also taking O(n) time. Within these nested loops, checking if a substring is a palindrome takes an additional O(n) time because it may involve comparing characters from both ends towards the middle. Therefore, the total time complexity is approximately n * n * n, simplifying to O(n³).

Space Complexity

O(n^2) – The brute force approach iterates through all possible substrings. In the worst case, to store all palindromic substrings found (or at least the longest one found so far), we might need to store a substring itself. A substring can have a length up to N, and we might potentially store multiple such substrings if we were to collect all of them. However, a more optimized version of brute force would only store the longest palindrome found so far. Even then, the characters of the longest palindrome could take O(N) space. Crucially, if the implementation checks if a substring is a palindrome by creating a reversed copy, this copy would take O(k) space where k is the substring length. Since k can be up to N, and this check happens within nested loops that examine O(N^2) substrings, the temporary space for the reversed string contributes to the overall space complexity. Therefore, the auxiliary space complexity is O(N) for storing the longest palindrome and O(N) for temporary string operations within the check, leading to an overall auxiliary space complexity of O(N).

Optimal Solution

Approach

The most efficient way to find the longest palindrome is to consider every possible center of a palindrome and expand outwards. This avoids checking every single substring and instead intelligently checks for palindromes around potential middle points.

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

Imagine each character as a potential middle of a palindrome. Also, imagine the space between every two characters as a potential middle.
For each potential middle, start with that single character or empty space and expand outwards in both directions, one character at a time.
As you expand, check if the characters on the left and right still match. If they do, keep expanding. If they don't, stop for this middle point.
Keep track of the longest palindrome found so far as you expand from each middle.
After checking all possible middle points, the longest one you recorded is your answer.

Code Implementation

def longest_palindromic_substring(input_string):
    if not input_string:
        return ""

    start_index_of_longest_palindrome = 0
    end_index_of_longest_palindrome = 0

    def expand_around_center(left_pointer, right_pointer):
        nonlocal start_index_of_longest_palindrome
        nonlocal end_index_of_longest_palindrome

        # Expand outwards as long as characters match and pointers are within bounds.
        while left_pointer >= 0 and right_pointer < len(input_string) and input_string[left_pointer] == input_string[right_pointer]:
            current_length = right_pointer - left_pointer + 1
            longest_length_so_far = end_index_of_longest_palindrome - start_index_of_longest_palindrome + 1

            # Update the longest palindrome found if the current one is longer.
            if current_length > longest_length_so_far:
                start_index_of_longest_palindrome = left_pointer
                end_index_of_longest_palindrome = right_pointer

            left_pointer -= 1
            right_pointer += 1

    # Iterate through each character as a potential center for an odd-length palindrome.
    for i in range(len(input_string)):
        expand_around_center(i, i)

    # Iterate through spaces between characters as potential centers for even-length palindromes.
    for i in range(len(input_string) - 1):
        expand_around_center(i, i + 1)

    # Return the longest palindromic substring found.
    return input_string[start_index_of_longest_palindrome : end_index_of_longest_palindrome + 1]

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through each character and each space between characters as a potential center of a palindrome. There are 2n-1 such potential centers. For each center, we expand outwards. In the worst case, this expansion can traverse up to n/2 characters in each direction. Therefore, the total number of character comparisons is roughly proportional to (2n-1) * (n/2), which simplifies to O(n^2).

Space Complexity

O(1) – The solution maintains only a few variables to store the start and end indices of the longest palindrome found so far, and the current left and right pointers during expansion. These variables do not grow with the input string length N. No auxiliary data structures that depend on N are created. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Empty input string	An empty string should return an empty string as the longest palindromic substring.
Input string with a single character	A single character string is a palindrome by definition, so it should be returned as is.
Input string with all identical characters	The entire string itself is the longest palindromic substring in this scenario.
Input string with no palindromic substrings longer than one character	The algorithm should correctly identify and return any single character as the longest palindromic substring.
Input string is itself a palindrome	The algorithm should correctly return the entire input string as the longest palindromic substring.
Very long input strings	The chosen algorithm (e.g., Manacher's algorithm or expanding around center) must be efficient enough (O(n^2) or O(n)) to handle large inputs without timing out.
Multiple longest palindromic substrings of the same length	The problem statement implies returning any one of them is acceptable; the algorithm's behavior in tie-breaking should be consistent.
Strings containing special characters or Unicode characters	The algorithm should treat all characters equally and correctly identify palindromes regardless of character type.

Empty input string

How to Handle:

An empty string should return an empty string as the longest palindromic substring.

Input string with a single character

How to Handle:

A single character string is a palindrome by definition, so it should be returned as is.

Input string with all identical characters

How to Handle:

The entire string itself is the longest palindromic substring in this scenario.

Input string with no palindromic substrings longer than one character

How to Handle:

The algorithm should correctly identify and return any single character as the longest palindromic substring.

Input string is itself a palindrome

How to Handle:

The algorithm should correctly return the entire input string as the longest palindromic substring.

Very long input strings

How to Handle:

The chosen algorithm (e.g., Manacher's algorithm or expanding around center) must be efficient enough (O(n^2) or O(n)) to handle large inputs without timing out.

Multiple longest palindromic substrings of the same length

How to Handle:

The problem statement implies returning any one of them is acceptable; the algorithm's behavior in tie-breaking should be consistent.

Strings containing special characters or Unicode characters

How to Handle:

The algorithm should treat all characters equally and correctly identify palindromes regardless of character type.

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 `s`? Can it be empty, or very long?
Are there any restrictions on the characters that can be present in the string `s` (e.g., only lowercase English letters, uppercase, digits, special characters)?
If there are multiple palindromic substrings of the same maximum length, which one should I return (e.g., the first one encountered, the last one)?
Is it possible for the input string to be null or undefined?
Does the problem statement imply any specific character encoding or collation rules that might affect palindrome checks?

Brute Force Solution

Approach

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

Consider every possible starting point for a potential substring within the original text.
From each starting point, consider every possible ending point to form a substring.
For every substring you create, check if it is a palindrome. A palindrome is something that reads the same forwards and backward.
Keep track of all the substrings that you find to be palindromes.
After checking all possible substrings, select the longest one from the list of palindromes you've collected.

Code Implementation

def longest_palindromic_substring_brute_force(input_string):    longest_palindrome_found = ""    # We need to check every possible substring, so we iterate through all start and end points.    for starting_index in range(len(input_string)):        for ending_index in range(starting_index, len(input_string)):            current_substring = input_string[starting_index : ending_index + 1]            # A palindrome reads the same forwards and backwards.            if current_substring == current_substring[::-1]:                # We update our longest palindrome if the current one is longer.                if len(current_substring) > len(longest_palindrome_found):                    longest_palindrome_found = current_substring    return longest_palindrome_found

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine each character as a potential middle of a palindrome. Also, imagine the space between every two characters as a potential middle.
For each potential middle, start with that single character or empty space and expand outwards in both directions, one character at a time.
As you expand, check if the characters on the left and right still match. If they do, keep expanding. If they don't, stop for this middle point.
Keep track of the longest palindrome found so far as you expand from each middle.
After checking all possible middle points, the longest one you recorded is your answer.

Code Implementation

def longest_palindromic_substring(input_string):
    if not input_string:
        return ""

    start_index_of_longest_palindrome = 0
    end_index_of_longest_palindrome = 0

    def expand_around_center(left_pointer, right_pointer):
        nonlocal start_index_of_longest_palindrome
        nonlocal end_index_of_longest_palindrome

        # Expand outwards as long as characters match and pointers are within bounds.
        while left_pointer >= 0 and right_pointer < len(input_string) and input_string[left_pointer] == input_string[right_pointer]:
            current_length = right_pointer - left_pointer + 1
            longest_length_so_far = end_index_of_longest_palindrome - start_index_of_longest_palindrome + 1

            # Update the longest palindrome found if the current one is longer.
            if current_length > longest_length_so_far:
                start_index_of_longest_palindrome = left_pointer
                end_index_of_longest_palindrome = right_pointer

            left_pointer -= 1
            right_pointer += 1

    # Iterate through each character as a potential center for an odd-length palindrome.
    for i in range(len(input_string)):
        expand_around_center(i, i)

    # Iterate through spaces between characters as potential centers for even-length palindromes.
    for i in range(len(input_string) - 1):
        expand_around_center(i, i + 1)

    # Return the longest palindromic substring found.
    return input_string[start_index_of_longest_palindrome : end_index_of_longest_palindrome + 1]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string	An empty string should return an empty string as the longest palindromic substring.
Input string with a single character	A single character string is a palindrome by definition, so it should be returned as is.
Input string with all identical characters	The entire string itself is the longest palindromic substring in this scenario.
Input string with no palindromic substrings longer than one character	The algorithm should correctly identify and return any single character as the longest palindromic substring.
Input string is itself a palindrome	The algorithm should correctly return the entire input string as the longest palindromic substring.
Very long input strings	The chosen algorithm (e.g., Manacher's algorithm or expanding around center) must be efficient enough (O(n^2) or O(n)) to handle large inputs without timing out.
Multiple longest palindromic substrings of the same length	The problem statement implies returning any one of them is acceptable; the algorithm's behavior in tie-breaking should be consistent.
Strings containing special characters or Unicode characters	The algorithm should treat all characters equally and correctly identify palindromes regardless of character type.

Empty input string

How to Handle:

An empty string should return an empty string as the longest palindromic substring.

Input string with a single character

How to Handle:

A single character string is a palindrome by definition, so it should be returned as is.

Input string with all identical characters

How to Handle:

The entire string itself is the longest palindromic substring in this scenario.

Input string with no palindromic substrings longer than one character

How to Handle:

The algorithm should correctly identify and return any single character as the longest palindromic substring.

Input string is itself a palindrome

How to Handle:

The algorithm should correctly return the entire input string as the longest palindromic substring.

Very long input strings

How to Handle:

The chosen algorithm (e.g., Manacher's algorithm or expanding around center) must be efficient enough (O(n^2) or O(n)) to handle large inputs without timing out.

Multiple longest palindromic substrings of the same length

How to Handle:

The problem statement implies returning any one of them is acceptable; the algorithm's behavior in tie-breaking should be consistent.

Strings containing special characters or Unicode characters

How to Handle:

The algorithm should treat all characters equally and correctly identify palindromes regardless of character type.

0/4 Netskope questions completed

0/4 completed