Lexicographically Smallest Palindrome

Easy

Asked by:

97 views

Topics:

StringsTwo Pointers

You are given a string s consisting of lowercase English letters, and you are allowed to perform operations on it. In one operation, you can replace a character in s with another lowercase English letter.

Your task is to make s a palindrome with the minimum number of operations possible. If there are multiple palindromes that can be made using the minimum number of operations, make the lexicographically smallest one.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Return the resulting palindrome string.

Example 1:

Input: s = "egcfe"
Output: "efcfe"
Explanation: The minimum number of operations to make "egcfe" a palindrome is 1, and the lexicographically smallest palindrome string we can get by modifying one character is "efcfe", by changing 'g'.

Example 2:

Input: s = "abcd"
Output: "abba"
Explanation: The minimum number of operations to make "abcd" a palindrome is 2, and the lexicographically smallest palindrome string we can get by modifying two characters is "abba".

Example 3:

Input: s = "seven"
Output: "neven"
Explanation: The minimum number of operations to make "seven" a palindrome is 1, and the lexicographically smallest palindrome string we can get by modifying one character is "neven".

Constraints:

1 <= s.length <= 1000
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:

What is the maximum length of the input string s?
Is the input string guaranteed to only contain lowercase English letters, or should I handle other characters?
If the input string is already a palindrome, should I return it as is?
Are there any special considerations for an empty input string?
In the case of multiple characters needing to be changed to form a palindrome, should I prioritize changing characters closer to the beginning of the string to achieve the lexicographically smallest result?

Brute Force Solution

Approach

The brute force strategy to make a word a palindrome involves trying all possible letter changes. We will explore every combination of changes to the input word, making sure the result is always a palindrome. Then, we pick the smallest palindrome we made by comparing them all.

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

Consider the first letter of the word and the last letter of the word. If they are different, try changing the last letter to match the first, and also try changing the first letter to match the last. That's two possibilities.
Now look at the second letter and the second-to-last letter. Again, if they're different, try changing the second-to-last to match the second, and vice versa. Now you have even more combinations to consider, combining these changes with the changes you made in the previous step.
Continue this process, moving inward from the ends of the word, considering each pair of letters and trying all possible changes to make them the same.
Each time you make a change, make sure to 'remember' the resulting word.
After you've tried all possible combinations of changes to all the letter pairs, you'll have a list of palindromes you've created.
Go through this list and find the palindrome that comes first alphabetically. This is the lexicographically smallest palindrome.

Code Implementation

def find_lexicographically_smallest_palindrome_brute_force(word):
    palindrome_candidates = []
    
    def generate_palindromes(current_word, index):
        if index >= len(current_word) // 2:
            palindrome_candidates.append("".join(current_word))
            return

        left_character = current_word[index]
        right_character = current_word[len(current_word) - 1 - index]

        if left_character == right_character:
            generate_palindromes(current_word, index + 1)
        else:
            # Create one branch to change the right character to match the left
            temp_word_one = list(current_word)
            temp_word_one[len(current_word) - 1 - index] = left_character

            generate_palindromes(temp_word_one, index + 1)

            # Create another branch to change the left character to match the right
            temp_word_two = list(current_word)
            temp_word_two[index] = right_character

            generate_palindromes(temp_word_two, index + 1)

    generate_palindromes(list(word), 0)

    # Ensure there are palindromes to compare
    if not palindrome_candidates:
        return ""
    
    smallest_palindrome = palindrome_candidates[0]

    # Now iterate through all possible palindromes and return the one that is smallest
    for palindrome in palindrome_candidates:
        if palindrome < smallest_palindrome:
            smallest_palindrome = palindrome

    return smallest_palindrome

Big(O) Analysis

Time Complexity

O(2^(n/2)) – The algorithm considers pairs of characters from the beginning and end of the string of length n, effectively looking at n/2 pairs. For each pair, if the characters differ, it explores two possibilities: changing the left character to match the right, or changing the right character to match the left. This branching creates a binary tree of possibilities where each level represents a pair of characters. Therefore, the number of possible palindromes generated and checked is proportional to 2 raised to the power of the number of differing character pairs, which can be at most n/2. Thus, the time complexity is O(2^(n/2)).

Space Complexity

O(2^N) – The brute force approach generates all possible palindromes by trying different letter changes. For each of the N/2 pairs of characters that need to be considered to make the word a palindrome, we explore up to two possibilities: changing the first letter to the second or changing the second letter to the first. This branching leads to a maximum of 2^(N/2) possible palindrome combinations being generated and 'remembered'. Therefore, the space needed to store these palindromes grows exponentially with the input size N, which simplifies to O(2^N).

Optimal Solution

Approach

The goal is to make the word read the same forwards and backward, while also making it as early as possible in the dictionary. We can achieve this by carefully comparing characters from the beginning and end of the word and making strategic replacements.

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

Look at the first and last letters of the word.
If the first letter comes before the last letter in the alphabet, and they are different, change the last letter to match the first letter.
If the last letter comes before the first letter in the alphabet, and they are different, change the first letter to match the last letter.
If the letters are the same, do nothing and move to the next pair.
Repeat this process, moving inwards from both ends of the word one letter at a time.
By always choosing the earlier letter in the alphabet when making changes, and always making the word a palindrome, we arrive at the optimal answer.

Code Implementation

def lexicographically_smallest_palindrome(input_string):
    string_list = list(input_string)
    left_index = 0
    right_index = len(string_list) - 1

    while left_index < right_index:
        # Ensure the smallest char is used for palindrome
        if string_list[left_index] < string_list[right_index]:

            string_list[right_index] = string_list[left_index]

        elif string_list[right_index] < string_list[left_index]:
            # Choose the smallest char for lexicographical order
            string_list[left_index] = string_list[right_index]

        # Move to the next pair of characters
        left_index += 1
        right_index -= 1

    return "".join(string_list)

Big(O) Analysis

Time Complexity

O(n) – The provided algorithm iterates through the input string 's' of length 'n' using two pointers, one starting from the beginning and the other from the end. In each iteration, it compares the characters at the two pointer locations and potentially modifies one of them to ensure the string becomes a palindrome. Each pointer moves towards the center of the string in each step. Therefore, the algorithm processes each character at most once, resulting in a single pass through the string. This single pass results in approximately 'n/2' comparisons and potentially 'n/2' modifications (in the worst case), simplifying to O(n).

Space Complexity

O(1) – The algorithm operates directly on the input string without creating any auxiliary data structures that scale with the input size N (the length of the word). It only uses a constant number of variables such as index pointers for comparing characters from both ends of the word. Therefore, the space complexity is constant, independent of the input string's length.

Edge Cases

Case	How to Handle
Empty string input	Return an empty string, as an empty string is already a palindrome.
Null string input	Throw an IllegalArgumentException or return null, depending on the preferred error handling.
Single character string	Return the string as is, as a single character string is already a palindrome.
String with two identical characters	Return the string as is, as it's already a palindrome.
String with two different characters	Change the larger character to the smaller one to make it the lexicographically smallest palindrome.
String with all identical characters	Return the string as is, since it's already a palindrome and no changes are necessary.
String with odd length and a mismatch in the middle	Handle mismatches in the first half of the string to preserve lexicographical order, and ensure the corresponding character in the second half is also updated.
String with maximum allowed length (performance check)	Ensure the solution operates within the time and space complexity constraints for the given input size, ideally O(n).

Empty string input

How to Handle:

Return an empty string, as an empty string is already a palindrome.

Null string input

How to Handle:

Throw an IllegalArgumentException or return null, depending on the preferred error handling.

Single character string

How to Handle:

Return the string as is, as a single character string is already a palindrome.

String with two identical characters

How to Handle:

Return the string as is, as it's already a palindrome.

String with two different characters

How to Handle:

Change the larger character to the smaller one to make it the lexicographically smallest palindrome.

String with all identical characters

How to Handle:

Return the string as is, since it's already a palindrome and no changes are necessary.

String with odd length and a mismatch in the middle

How to Handle:

Handle mismatches in the first half of the string to preserve lexicographical order, and ensure the corresponding character in the second half is also updated.

String with maximum allowed length (performance check)

How to Handle:

Ensure the solution operates within the time and space complexity constraints for the given input size, ideally O(n).