Lexicographically Smallest Palindrome Using Two-Pointer Approach
IntuitionA palindrome is a string that reads the same forward and backward. To transform a given string into a lexicographically smallest palindrome, we need to
---

# **Intuition**  
A **palindrome** is a string that reads the same forward and backward. To transform a given string into a **lexicographically smallest palindrome**, we need to modify the characters while ensuring minimal changes.  

A **lexicographically smaller** string means that, when comparing two characters, we replace the larger one with the smaller one to ensure the smallest possible result.

---

# **Approach**  
1. **Use Two Pointers:**  
   - Start with `i = 0` (leftmost character) and `j = s.length - 1` (rightmost character).  
   - Move `i` forward and `j` backward, ensuring that characters at `i` and `j` match.  
   
2. **Modify the String In-Place:**  
   - If `s[i] != s[j]`, replace both with the **smaller** character (`min(s[i], s[j])`).  
   - This ensures the lexicographically smallest result while making the string a palindrome.

3. **Convert Back to String:**  
   - Since strings are immutable in JavaScript, we first convert `s` into an array (`arr`) for modification.
   - After processing, we join the array back into a string.

---

# **Complexity Analysis**  
- **Time Complexity:** **\( O(n) \)**  
  - We traverse the string **once**, comparing and modifying characters, leading to linear time complexity.  

- **Space Complexity:** **\( O(n) \)**  
  - We create an array `arr` of size `n` to modify characters, leading to linear space complexity.  
  - However, if **mutability of the input string** were allowed, we could achieve **\( O(1) \)** space complexity.

---

# **Code**
```javascript
/**
 * @param {string} s
 * @return {string}
 */
var makeSmallestPalindrome = function(s) {
    let i = 0, j = s.length - 1;
    let arr = Array.from(s); // Convert string to array for modification
    
    while (i <= j) {
        if (arr[i] !== arr[j]) {
            const minChar = arr[i] < arr[j] ? arr[i] : arr[j]; // Choose the smaller character
            arr[i] = arr[j] = minChar; // Assign the same value to both sides
        }
        i++;
        j--;
    }
    
    return arr.join(""); // Convert array back to string
};

// Example Test Cases
console.log(makeSmallestPalindrome("egcfe")); // Output: "efcfe"
console.log(makeSmallestPalindrome("abcd"));  // Output: "abba"
console.log(makeSmallestPalindrome("race"));  // Output: "eace"
console.log(makeSmallestPalindrome("madam")); // Output: "madam" (Already a palindrome)
```

---

# **Example Walkthrough**  
### **Example 1:**
#### **Input:** `"egcfe"`  
#### **Processing Steps:**
| i | j | arr[i] | arr[j] | Modification | Updated String |
|---|---|--------|--------|--------------|----------------|
| 0 | 4 | 'e'    | 'e'    | No change    | "egcfe"        |
| 1 | 3 | 'g'    | 'f'    | Replace with 'f' | "efcfe" |
| 2 | 2 | 'c'    | 'c'    | No change    | "efcfe"        |

#### **Output:** `"efcfe"`

---

### **Example 2:**
#### **Input:** `"abcd"`
#### **Processing:**
| i | j | arr[i] | arr[j] | Modification | Updated String |
|---|---|--------|--------|--------------|----------------|
| 0 | 3 | 'a'    | 'd'    | Replace 'd' with 'a' | "abca" |
| 1 | 2 | 'b'    | 'c'    | Replace 'c' with 'b' | "abba" |

#### **Output:** `"abba"`

---

# **Summary**
✅ Uses the **two-pointer approach** to efficiently transform the string.  
✅ Ensures the **lexicographically smallest** palindrome with minimal modifications.  
✅ Achieves **\( O(n) \) time complexity** and **\( O(n) \) space complexity**.  
✅ Works for **both even- and odd-length strings**.  

['JavaScript']