Jobs

Interviews

Discussions

Longest Palindrome

Easy

Asked by:

More companies

44 views

Topics:

StringsGreedy Algorithms

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome.

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.

Constraints:

1 <= s.length <= 2000
s consists of lowercase and/or uppercase English letters only.

Try coding it in LeetCode

Longest Palindrome

Easy

Asked by:

44 views

Topics:

StringsGreedy Algorithms

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome.

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.

Constraints:

1 <= s.length <= 2000
s consists of lowercase and/or uppercase 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:

Can the input string be empty or null? If so, what should I return?
Are we only considering alphanumeric characters, or should I handle other characters like spaces and punctuation?
Is the palindrome case-sensitive (e.g., 'Racecar' vs. 'racecar')?
If there are multiple palindromes of the same maximum length, should I return any one of them, or is there a specific one I should prioritize?
What is the maximum length of the input string I should expect?

Brute Force Solution

Approach

To find the longest palindrome, a brute force strategy means we check every possible section of the given text. We'll look at each section, one by one, and see if it reads the same forwards and backward. We remember the longest one we've found so far.

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

Start by considering the first single character as a potential palindrome.
Then, consider the first two characters, then the first three, and so on, all the way to the end of the text.
For each of these 'sections' check if it is a palindrome - does it read the same way forward and backward?
If a section is a palindrome and it's longer than the longest one we've found so far, remember this new, longer palindrome.
Now, repeat this process, but starting with the second character. Check the section from the second character to the end, then from the second and third, and so on.
Continue doing this, each time starting at the next character in the original text, checking every possible section until we get to the last character.
Once we've checked every single section, the longest palindrome we remembered along the way is the answer.

Code Implementation

def longest_palindrome_brute_force(input_string):
    longest_palindrome = ""

    for start_index in range(len(input_string)):
        for end_index in range(start_index, len(input_string)):
            # Consider all possible substrings
            substring = input_string[start_index:end_index + 1]

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

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

    return longest_palindrome

Big(O) Analysis

Time Complexity

O(n³) – The outer loop iterates through each of the n characters in the string. The inner loop, for each starting character, iterates through all possible substrings starting from that character, resulting in another n iterations in the worst case. Within the inner loop, there's a palindrome check that iterates through the substring, which can also take up to n operations. Therefore, we have a nested loop structure with a function that can take up to n time, resulting in approximately n * n * n operations, which simplifies to O(n³).

Space Complexity

O(1) – The provided algorithm only stores a few variables: the longest palindrome found so far and potentially a few loop counters. The number of these variables remains constant regardless of the input string's length (N). No auxiliary data structures like arrays, hashmaps, or stacks are used, meaning the extra space required doesn't scale with the input size. Therefore, the space complexity is constant.

Optimal Solution

Approach

The most efficient way to find the longest palindrome involves expanding outwards from potential centers. Instead of checking every possible substring, we strategically examine areas that are more likely to be palindromes. This avoids redundant checks and quickly identifies the longest one.

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

Consider each letter in the given text as a potential middle point of a palindrome.
For each middle point, try to expand outwards, one letter at a time, in both directions.
If the letters on either side of the center match, that means the palindrome is getting longer; keep expanding.
If the letters don't match, then stop expanding; the current palindrome can't get any bigger.
Also, consider pairs of adjacent letters as potential middle points (for palindromes that have an even number of characters).
Keep track of the longest palindrome you've found so far.
After checking all possible middle points and expanding as much as possible from each, the longest palindrome you recorded is the answer.

Code Implementation

def longestPalindrome(input_string):
    longest_palindrome_so_far = ""
    string_length = len(input_string)

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

        # Expand around the center as long as possible.
        while left_index >= 0 and right_index < string_length and input_string[left_index] == input_string[right_index]:
            current_palindrome_length = right_index - left_index + 1
            if current_palindrome_length > len(longest_palindrome_so_far):
                longest_palindrome_so_far = input_string[left_index:right_index + 1]
            left_index -= 1
            right_index += 1

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

        # Need to check even palindromes
        while left_index >= 0 and right_index < string_length and input_string[left_index] == input_string[right_index]:
            current_palindrome_length = right_index - left_index + 1
            if current_palindrome_length > len(longest_palindrome_so_far):
                longest_palindrome_so_far = input_string[left_index:right_index + 1]
            left_index -= 1
            right_index += 1

    # Return the longest palindrome found
    return longest_palindrome_so_far

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each character of the input string of length n, considering each as a potential center of a palindrome. For each center, it expands outwards, potentially comparing characters on both sides until a mismatch is found or the string boundaries are reached. In the worst case, for each of the n centers, the expansion might cover a length proportional to n. Therefore, the total operations approximate n * n, resulting in a time complexity of O(n²).

Space Complexity

O(1) – The algorithm's space complexity is determined by the extra memory needed beyond the input string. The plain English explanation describes expanding from potential centers and tracking the longest palindrome found so far. This requires storing a few variables to keep track of the start and end indices or the length of the longest palindrome. The amount of extra memory used does not depend on the length of the input string (N), so the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string as an empty string is a palindrome of length 0
Single character string	Return the single character string itself, as it is a palindrome
String with two identical characters (e.g., 'aa')	Return the entire string as it is a palindrome
String with two different characters (e.g., 'ab')	Return the first character, as a single character is always a palindrome
String with all identical characters (e.g., 'aaaa')	Return the entire string, as it is a palindrome
Very long string to check for time complexity (e.g., 10000 'a's)	Dynamic programming approach or expanding around center provides optimal time complexity for large inputs.
String contains non-alphanumeric characters	Preprocess the string to remove non-alphanumeric characters or handle them based on problem's requirements.
String contains mixed case letters	Consider converting the entire string to lowercase before processing to handle case-insensitive palindromes.

Null or empty input string

How to Handle:

Return an empty string as an empty string is a palindrome of length 0

Single character string

How to Handle:

Return the single character string itself, as it is a palindrome

String with two identical characters (e.g., 'aa')

How to Handle:

Return the entire string as it is a palindrome

String with two different characters (e.g., 'ab')

How to Handle:

Return the first character, as a single character is always a palindrome

String with all identical characters (e.g., 'aaaa')

How to Handle:

Return the entire string, as it is a palindrome

Very long string to check for time complexity (e.g., 10000 'a's)

How to Handle:

Dynamic programming approach or expanding around center provides optimal time complexity for large inputs.

String contains non-alphanumeric characters

How to Handle:

Preprocess the string to remove non-alphanumeric characters or handle them based on problem's requirements.

String contains mixed case letters

How to Handle:

Consider converting the entire string to lowercase before processing to handle case-insensitive palindromes.

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 be empty or null? If so, what should I return?
Are we only considering alphanumeric characters, or should I handle other characters like spaces and punctuation?
Is the palindrome case-sensitive (e.g., 'Racecar' vs. 'racecar')?
If there are multiple palindromes of the same maximum length, should I return any one of them, or is there a specific one I should prioritize?
What is the maximum length of the input string I should expect?

Brute Force Solution

Approach

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

Start by considering the first single character as a potential palindrome.
Then, consider the first two characters, then the first three, and so on, all the way to the end of the text.
For each of these 'sections' check if it is a palindrome - does it read the same way forward and backward?
If a section is a palindrome and it's longer than the longest one we've found so far, remember this new, longer palindrome.
Now, repeat this process, but starting with the second character. Check the section from the second character to the end, then from the second and third, and so on.
Continue doing this, each time starting at the next character in the original text, checking every possible section until we get to the last character.
Once we've checked every single section, the longest palindrome we remembered along the way is the answer.

Code Implementation

def longest_palindrome_brute_force(input_string):
    longest_palindrome = ""

    for start_index in range(len(input_string)):
        for end_index in range(start_index, len(input_string)):
            # Consider all possible substrings
            substring = input_string[start_index:end_index + 1]

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

                # Update longest palindrome if current is longer
                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:

Consider each letter in the given text as a potential middle point of a palindrome.
For each middle point, try to expand outwards, one letter at a time, in both directions.
If the letters on either side of the center match, that means the palindrome is getting longer; keep expanding.
If the letters don't match, then stop expanding; the current palindrome can't get any bigger.
Also, consider pairs of adjacent letters as potential middle points (for palindromes that have an even number of characters).
Keep track of the longest palindrome you've found so far.
After checking all possible middle points and expanding as much as possible from each, the longest palindrome you recorded is the answer.

Code Implementation

def longestPalindrome(input_string):
    longest_palindrome_so_far = ""
    string_length = len(input_string)

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

        # Expand around the center as long as possible.
        while left_index >= 0 and right_index < string_length and input_string[left_index] == input_string[right_index]:
            current_palindrome_length = right_index - left_index + 1
            if current_palindrome_length > len(longest_palindrome_so_far):
                longest_palindrome_so_far = input_string[left_index:right_index + 1]
            left_index -= 1
            right_index += 1

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

        # Need to check even palindromes
        while left_index >= 0 and right_index < string_length and input_string[left_index] == input_string[right_index]:
            current_palindrome_length = right_index - left_index + 1
            if current_palindrome_length > len(longest_palindrome_so_far):
                longest_palindrome_so_far = input_string[left_index:right_index + 1]
            left_index -= 1
            right_index += 1

    # Return the longest palindrome found
    return longest_palindrome_so_far

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string as an empty string is a palindrome of length 0
Single character string	Return the single character string itself, as it is a palindrome
String with two identical characters (e.g., 'aa')	Return the entire string as it is a palindrome
String with two different characters (e.g., 'ab')	Return the first character, as a single character is always a palindrome
String with all identical characters (e.g., 'aaaa')	Return the entire string, as it is a palindrome
Very long string to check for time complexity (e.g., 10000 'a's)	Dynamic programming approach or expanding around center provides optimal time complexity for large inputs.
String contains non-alphanumeric characters	Preprocess the string to remove non-alphanumeric characters or handle them based on problem's requirements.
String contains mixed case letters	Consider converting the entire string to lowercase before processing to handle case-insensitive palindromes.

Null or empty input string

How to Handle:

Return an empty string as an empty string is a palindrome of length 0

Single character string

How to Handle:

Return the single character string itself, as it is a palindrome

String with two identical characters (e.g., 'aa')

How to Handle:

Return the entire string as it is a palindrome

String with two different characters (e.g., 'ab')

How to Handle:

Return the first character, as a single character is always a palindrome

String with all identical characters (e.g., 'aaaa')

How to Handle:

Return the entire string, as it is a palindrome

Very long string to check for time complexity (e.g., 10000 'a's)

How to Handle:

Dynamic programming approach or expanding around center provides optimal time complexity for large inputs.

String contains non-alphanumeric characters

How to Handle:

Preprocess the string to remove non-alphanumeric characters or handle them based on problem's requirements.

String contains mixed case letters

How to Handle:

Consider converting the entire string to lowercase before processing to handle case-insensitive palindromes.