Leetcode problem 82 - Lexicographically Smallest Palindrome

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”.

/**
 * @param {string} s
 * @return {string}
 */
var makeSmallestPalindrome = function (s) {
  // Convert the input string 's' into an array of characters
  let str = s.split("");

  // Loop through the characters, comparing and updating symmetric pairs
  for (let i = s.length - 1, j = 0; i >= Math.ceil(s.length / 2); i--, j++) {
    // Check if the character at position 'i' is less than the character at position 'j'
    if (str[i] < str[j]) {
      // If true, update the character at position 'j' to be the same as the character at position 'i'
      str[j] = str[i];
    } else {
      // If false, update the character at position 'i' to be the same as the character at position 'j'
      str[i] = str[j];
    }
  }

  // Join the modified array of characters back into a string and return the result
  return str.join("");
};

The makeSmallestPalindrome function takes an input string s, converts it into an array of characters, and iterates over the characters, updating pairs symmetrically from the middle towards both ends. If a character on the right side is smaller than its corresponding character on the left side, it updates the character on the left side to match the smaller one. The process ensures that the resulting string is lexicographically smallest or equal to its mirror reflection. The time complexity of the algorithm is O(n/2), where n is the length of the input string, as the loop iterates over half of the string. The space complexity is O(n) due to the array created to store the characters of the input string.