# Lexicographically Smallest Palindrome
**Difficulty:** EASY
[External](https://leetcode.com/problems/lexicographically-smallest-palindrome)
Canonical: https://scaleengineer.com/dsa/problems/lexicographically-smallest-palindrome
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal)
---
## Problem
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
## 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.
**Time:** 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:** 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:** 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.
### Explanation
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.<br><br>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.<br><br>```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;
    }
}
```
### Algorithm
*   Initialize an empty string, `palindrome`.<br>*   Iterate with an index `i` from `0` to `n-1`, where `n` is the length of the input string `s`.<br>*   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)`.<br>*   Append the lexicographically smaller of `char1` and `char2` to the `palindrome` string.<br>*   After the loop completes, return the `palindrome` string.

## Two-Pointer In-place Modification
This is the optimal approach, utilizing a two-pointer technique to achieve linear time complexity. It iterates through the string from both ends simultaneously, moving inwards. By converting the immutable string to a mutable `char` array, it can perform modifications efficiently. This method ensures minimum operations and the lexicographically smallest result in a single pass.
**Time:** O(N), where N is the length of the string. The process involves a single pass through roughly half of the string. Converting to and from a char array also takes O(N) time. · **Space:** O(N). An additional character array of size N is required to store the mutable version of the string, as strings are immutable in Java.
**Pros:** Highly efficient with linear time complexity.; Optimal solution for this problem.; Easy to implement and understand.
**Cons:** Requires extra space for the character array due to string immutability in Java. This is generally an accepted trade-off.
### Explanation
To make a string a palindrome, the character at index `i` must equal the character at `n-1-i`. If they differ, we must change at least one. To minimize operations, we perform one change. To get the lexicographically smallest palindrome, we must make both positions equal to the smaller of the two original characters. This ensures the character at the earlier index `i` is as small as possible.<br><br>The two-pointer approach is a natural fit for this symmetric problem. A `left` pointer starts at the beginning, and a `right` pointer starts at the end. They move towards each other. At each step, they ensure the characters `chars[left]` and `chars[right]` are made equal to the smaller of the two, thus building the lexicographically smallest palindrome.<br><br>Since strings are immutable in Java, the input string is first converted to a `char` array to allow for efficient in-place modifications. After the two-pointer traversal is complete, the array is converted back to a string.<br><br>```java
class Solution {
    public String makeSmallestPalindrome(String s) {
        char[] chars = s.toCharArray();
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            if (chars[left] != chars[right]) {
                if (chars[left] < chars[right]) {
                    chars[right] = chars[left];
                } else {
                    chars[left] = chars[right];
                }
            }
            left++;
            right--;
        }
        return new String(chars);
    }
}
```
### Algorithm
*   Convert the input string `s` into a character array, `chars`.<br>*   Initialize two pointers: `left = 0` and `right = s.length() - 1`.<br>*   Loop as long as `left` is less than `right`.<br>*   Inside the loop, compare `chars[left]` and `chars[right]`.<br>*   If they are different, set both positions to be the smaller of the two characters. For instance, if `chars[left] < chars[right]`, set `chars[right] = chars[left]`. Otherwise, set `chars[left] = chars[right]`.<br>*   Move the pointers towards the center by incrementing `left` and decrementing `right`.<br>*   After the loop, create a new string from the modified `chars` array and return it.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string makeSmallestPalindrome(string s) {
    for (int i = 0, j = s.size() - 1; i < j; ++i, --j) {
      s[i] = s[j] = min(s[i], s[j]);
    }
    return s;
  }
};

```

### Python

```python
class Solution:
    def makeSmallestPalindrome(self, s: str) -> str: cs = list(s) i, j = 0, len(s) - 1 while i < j: cs[i] = cs[j] = min(cs[i], cs[j]) i, j = i + 1, j - 1 return "" . join(cs)

```