Jobs

Interviews

Discussions

Palindrome Permutation

Easy

Asked by:

More companies

114 views

Topics:

Strings

Given a string s, return true if a permutation of the string could form a palindrome.

Example 1:

Input: s = "code"
Output: false

Example 2:

Input: s = "aab"
Output: true
Explanation: It can be permuted into "aba".

Example 3:

Input: s = "carerac"
Output: true
Explanation: It can be permuted into "racecar".

Constraints:

1 <= s.length <= 5000
s consists of only lowercase English letters.

Try coding it in LeetCode

Palindrome Permutation

Easy

Asked by:

114 views

Topics:

Strings

Given a string s, return true if a permutation of the string could form a palindrome.

Example 1:

Input: s = "code"
Output: false

Example 2:

Input: s = "aab"
Output: true
Explanation: It can be permuted into "aba".

Example 3:

Input: s = "carerac"
Output: true
Explanation: It can be permuted into "racecar".

Constraints:

1 <= s.length <= 5000
s consists of only lowercase 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:

Is the input string case-sensitive? For example, should "Racecar" be considered a palindrome?
Can the input string contain non-alphanumeric characters (e.g., spaces, punctuation)? If so, should they be considered?
Can the input string be empty or null? If so, what should the function return?
Is there a limit to the length of the input string?
Are we concerned with Unicode characters or just ASCII?

Brute Force Solution

Approach

The brute force approach to solving the palindrome permutation problem is quite simple: we will check every possible arrangement of the input string's characters. If any of these arrangements form a palindrome, then the original string is a permutation of a palindrome.

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

Take the given string.
Generate every possible arrangement (permutation) of the characters in the string.
For each of these arrangements, check if it is a palindrome (reads the same forwards and backward).
If any of the arrangements is a palindrome, then we can say the original string is a permutation of a palindrome.
If we have checked all possible arrangements and none of them are palindromes, then the original string is not a permutation of a palindrome.

Code Implementation

def palindrome_permutation_brute_force(input_string):
    import itertools

    # Generate all possible permutations of the input string
    all_permutations = itertools.permutations(input_string)

    # Check each permutation to see if it is a palindrome
    for possible_permutation in all_permutations:
        stringified_permutation = ''.join(possible_permutation)
        if stringified_permutation == stringified_permutation[::-1]:

            # Found a palindromic permutation, so return True
            return True

    # If no permutation is a palindrome, the original string isn't
    return False

Big(O) Analysis

Time Complexity

O(n!) – The algorithm generates all possible permutations of the input string, which contains n characters. Generating all permutations takes O(n!) time. For each permutation, the algorithm checks if it is a palindrome, which takes O(n) time. Thus, the overall time complexity is O(n! * n). Because the factorial component dominates, the time complexity can be simplified to O(n!).

Space Complexity

O(N!) – The brute force approach generates all possible permutations of the input string of length N. Generating permutations often involves storing intermediate permutations, which in the worst-case scenario, can grow to a size proportional to the number of permutations. The number of permutations of a string of length N is N! (N factorial). Therefore, the auxiliary space required to store these permutations can be on the order of N!.

Optimal Solution

Approach

The core idea is that a string can form a palindrome only if it has at most one character that appears an odd number of times. This is because in a palindrome, almost all characters must pair up. We can check this condition efficiently without rearranging the string.

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

Count how many times each character appears in the input string.
Check how many characters appear an odd number of times.
If more than one character appears an odd number of times, the string cannot be rearranged into a palindrome. It's impossible.
If zero or one character appears an odd number of times, the string can be rearranged to form a palindrome. It's possible.

Code Implementation

def can_form_palindrome(input_string):
    character_counts = {}
    for character in input_string:
        character_counts[character] = character_counts.get(character, 0) + 1

    odd_count = 0
    # Count characters appearing an odd number of times
    for character in character_counts:
        if character_counts[character] % 2 != 0:
            odd_count += 1

    # A palindrome can have at most one character with an odd count
    if odd_count > 1:
        return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm first counts the frequency of each character in the input string of size n. This involves iterating through the string once, resulting in O(n) time complexity. Then, it iterates through the character counts to determine how many characters appear an odd number of times. In the worst case, this iteration could go through all unique characters which is bounded by n (the length of the string). Thus, the second step is also O(n). Therefore, the overall time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(1) – The algorithm uses a character counter, which can be implemented with a hash map or an array. In the worst case, if the string has all unique characters within a defined character set (e.g., ASCII or Unicode), the counter's size would be bounded by the size of that character set, which is constant. The algorithm also uses a single variable to track the number of characters with odd counts. Thus, the space complexity is O(1), constant with respect to the input string length N.

Edge Cases

Case	How to Handle
Null or empty string input	Return true, as an empty string is technically a palindrome.
Single character string	Return true, as a single character string is always a palindrome.
String with all identical characters	Return true, any permutation of such string forms a palindrome.
String with ASCII characters	The solution needs to accommodate ASCII character set (256 possible characters), so use a sufficiently sized data structure (e.g., array of size 256 or a hash map).
String with mixed case characters	Convert the string to lowercase or uppercase to ensure case-insensitive comparison.
Very long string (performance implications)	The solution should use a hash map or fixed-size array instead of sorting, which offers better time complexity O(n) instead of O(n log n).
String with non-alphanumeric characters (spaces, punctuation)	Filter out non-alphanumeric characters or handle them according to the problem specification if they matter.
String has only one character that appears an odd number of times, and the rest appear an even number of times.	The algorithm should correctly identify the string as a potential palindrome.

Null or empty string input

How to Handle:

Return true, as an empty string is technically a palindrome.

Single character string

How to Handle:

Return true, as a single character string is always a palindrome.

String with all identical characters

How to Handle:

Return true, any permutation of such string forms a palindrome.

String with ASCII characters

How to Handle:

The solution needs to accommodate ASCII character set (256 possible characters), so use a sufficiently sized data structure (e.g., array of size 256 or a hash map).

String with mixed case characters

How to Handle:

Convert the string to lowercase or uppercase to ensure case-insensitive comparison.

Very long string (performance implications)

How to Handle:

The solution should use a hash map or fixed-size array instead of sorting, which offers better time complexity O(n) instead of O(n log n).

String with non-alphanumeric characters (spaces, punctuation)

How to Handle:

Filter out non-alphanumeric characters or handle them according to the problem specification if they matter.

String has only one character that appears an odd number of times, and the rest appear an even number of times.

How to Handle:

The algorithm should correctly identify the string as a potential palindrome.

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:

Is the input string case-sensitive? For example, should "Racecar" be considered a palindrome?
Can the input string contain non-alphanumeric characters (e.g., spaces, punctuation)? If so, should they be considered?
Can the input string be empty or null? If so, what should the function return?
Is there a limit to the length of the input string?
Are we concerned with Unicode characters or just ASCII?

Brute Force Solution

Approach

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

Take the given string.
Generate every possible arrangement (permutation) of the characters in the string.
For each of these arrangements, check if it is a palindrome (reads the same forwards and backward).
If any of the arrangements is a palindrome, then we can say the original string is a permutation of a palindrome.
If we have checked all possible arrangements and none of them are palindromes, then the original string is not a permutation of a palindrome.

Code Implementation

def palindrome_permutation_brute_force(input_string):
    import itertools

    # Generate all possible permutations of the input string
    all_permutations = itertools.permutations(input_string)

    # Check each permutation to see if it is a palindrome
    for possible_permutation in all_permutations:
        stringified_permutation = ''.join(possible_permutation)
        if stringified_permutation == stringified_permutation[::-1]:

            # Found a palindromic permutation, so return True
            return True

    # If no permutation is a palindrome, the original string isn't
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Count how many times each character appears in the input string.
Check how many characters appear an odd number of times.
If more than one character appears an odd number of times, the string cannot be rearranged into a palindrome. It's impossible.
If zero or one character appears an odd number of times, the string can be rearranged to form a palindrome. It's possible.

Code Implementation

def can_form_palindrome(input_string):
    character_counts = {}
    for character in input_string:
        character_counts[character] = character_counts.get(character, 0) + 1

    odd_count = 0
    # Count characters appearing an odd number of times
    for character in character_counts:
        if character_counts[character] % 2 != 0:
            odd_count += 1

    # A palindrome can have at most one character with an odd count
    if odd_count > 1:
        return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return true, as an empty string is technically a palindrome.
Single character string	Return true, as a single character string is always a palindrome.
String with all identical characters	Return true, any permutation of such string forms a palindrome.
String with ASCII characters	The solution needs to accommodate ASCII character set (256 possible characters), so use a sufficiently sized data structure (e.g., array of size 256 or a hash map).
String with mixed case characters	Convert the string to lowercase or uppercase to ensure case-insensitive comparison.
Very long string (performance implications)	The solution should use a hash map or fixed-size array instead of sorting, which offers better time complexity O(n) instead of O(n log n).
String with non-alphanumeric characters (spaces, punctuation)	Filter out non-alphanumeric characters or handle them according to the problem specification if they matter.
String has only one character that appears an odd number of times, and the rest appear an even number of times.	The algorithm should correctly identify the string as a potential palindrome.

Null or empty string input

How to Handle:

Return true, as an empty string is technically a palindrome.

Single character string

How to Handle:

Return true, as a single character string is always a palindrome.

String with all identical characters

How to Handle:

Return true, any permutation of such string forms a palindrome.

String with ASCII characters

How to Handle:

The solution needs to accommodate ASCII character set (256 possible characters), so use a sufficiently sized data structure (e.g., array of size 256 or a hash map).

String with mixed case characters

How to Handle:

Convert the string to lowercase or uppercase to ensure case-insensitive comparison.

Very long string (performance implications)

How to Handle:

The solution should use a hash map or fixed-size array instead of sorting, which offers better time complexity O(n) instead of O(n log n).

String with non-alphanumeric characters (spaces, punctuation)

How to Handle:

Filter out non-alphanumeric characters or handle them according to the problem specification if they matter.

String has only one character that appears an odd number of times, and the rest appear an even number of times.

How to Handle:

The algorithm should correctly identify the string as a potential palindrome.