We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Lexicographically Smallest Palindrome

Difficulty: Easy

Problem Description

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. Return the resulting palindrome string.

Key Insights

  • A palindrome reads the same forwards and backwards.
  • To transform a string into a palindrome, we only need to ensure that characters at symmetric positions from the start and end of the string are equal.
  • If characters differ, we can choose to replace either character with the other or with a smaller character to ensure lexicographical order.
  • We can use a two-pointer approach, one starting from the beginning and the other from the end of the string, to efficiently check and modify characters.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a two-pointer technique:

  1. Initialize two pointers: one at the start (left) and one at the end (right) of the string.
  2. Iterate while the left pointer is less than or equal to the right pointer.
  3. If the characters at left and right are the same, move both pointers inward.
  4. If they differ, replace both characters with the lexicographically smaller character between them.
  5. Continue until the entire string is processed.
  6. Return the modified string.

This approach ensures we only traverse the string once, making it efficient.

Code Solutions

def makeSmallestPalindrome(s: str) -> str:
    s = list(s)  # Convert string to a list for mutability
    left, right = 0, len(s) - 1  # Initialize two pointers
    while left <= right:
        if s[left] != s[right]:  # Check if characters are different
            # Replace both with the smaller character
            smaller_char = min(s[left], s[right])
            s[left] = smaller_char
            s[right] = smaller_char
        left += 1  # Move left pointer to the right
        right -= 1  # Move right pointer to the left
    return ''.join(s)  # Join list back to string
← Back to All Questions