Lexicographically Smallest Palindrome

EASY

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.

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.

Approaches

Checkout 2 different approaches to solve Lexicographically Smallest Palindrome. Click on different approaches to view the approach and algorithm in detail.

Inefficient String Concatenation

This approach constructs the palindrome by iterating through the string and building a new result string. For each position i, it considers the character s.charAt(i) and its symmetric counterpart s.charAt(n-1-i). To satisfy the conditions of minimum operations and lexicographically smallest result, the smaller of these two characters is chosen. The main drawback of this method is using string concatenation inside a loop in Java, which is very inefficient and leads to quadratic time complexity.

Algorithm

Initialize an empty string, palindrome. * Iterate with an index i from 0 to n-1, where n is the length of the input string s. * In each iteration, get the character at the current index, char1 = s.charAt(i), and the character at the symmetric index, char2 = s.charAt(n - 1 - i). * Append the lexicographically smaller of char1 and char2 to the palindrome string. * After the loop completes, return the palindrome string.

This approach correctly identifies that the character at any position i in the final palindrome should be the minimum of the original characters at i and n-1-i. It then builds the resulting string character by character from left to right. The inefficiency stems from the implementation detail of using the += operator for string concatenation within a loop. In Java, strings are immutable. Each concatenation operation result += char creates a completely new string object and copies all the characters from the old result string plus the new character. If the loop runs N times, the total number of copy operations is proportional to the sum 1 + 2 + ... + (N-1), which results in an O(N^2) time complexity. ```java class Solution { public String makeSmallestPalindrome(String s) { int n = s.length(); String palindrome = ""; // Inefficient string building for (int i = 0; i < n; i++) { char char1 = s.charAt(i); char char2 = s.charAt(n - 1 - i); if (char1 < char2) { palindrome += char1; } else { palindrome += char2; } } return palindrome; } }

Complexity Analysis

Time Complexity: O(N^2), where N is the length of the string. The loop runs N times, and string concatenation inside the loop takes O(N) time on average, leading to a quadratic overall complexity.Space Complexity: O(N^2) in many Java environments. During the loop, intermediate strings of lengths 1, 2, ..., N-1 are created and discarded. The final output string occupies O(N) space, but the peak space usage during execution can be much higher.

Pros and Cons

Pros:

The logic is straightforward to conceptualize.

Cons:

Extremely inefficient in terms of time and space.
Will likely cause a 'Time Limit Exceeded' (TLE) error for constraints like N=1000.

Code Solutions

Checking out 3 solutions in different languages for Lexicographically Smallest Palindrome. Click on different languages to view the code.

class Solution {
public
  String makeSmallestPalindrome(String s) {
    char[] cs = s.toCharArray();
    for (int i = 0, j = cs.length - 1; i < j; ++i, --j) {
      cs[i] = cs[j] = (char)Math.min(cs[i], cs[j]);
    }
    return new String(cs);
  }
}

Video Solution

Watch the video walkthrough for Lexicographically Smallest Palindrome

Patterns:

Two PointersGreedy

Data Structures:

String

Companies:

PayPal |