algoadvance

Leetcode 2697. Lexicographically Smallest Palindrome

Problem Statement

Given a string s of length n consisting of only lowercase English letters, convert it into a palindrome by changing some (possibly zero) characters such that the resulting palindrome is lexicographically smallest among all possible palindromes you can obtain in this way.

Clarifying Questions

1. Input Constraints:
   • What is the maximum length of the string s?
     • Assume that (1 \leq n \leq 10^5).
   • Can s be an empty string?
     • No, it will have a length of at least 1.
2. Output Requirements:
   • Should the output also be a string of lowercase English letters?
     • Yes.
   • What if the input string is already a palindrome? Should we still apply any changes?
     • If it’s already the smallest lexicographical palindrome, no changes are required.

Strategy

1. Palindrome Property:
   • A string is a palindrome if it reads the same forwards and backwards. For s to be a palindrome, s[i] must equal s[n-1-i].
2. Lexicographically Smallest:
   • To ensure the palindrome is lexicographically smallest, whenever matching characters from each end (i.e., s[i] and s[n-1-i]), change them to the smallest possible character if they do not match.
3. Two-Pointer Approach:
   • Initialize two pointers: left at 0 and right at n-1.
   • Traverse towards the center:
     • If s[left] != s[right], set both to the minimum of the two.
     • Choose the minimum character for both s[left] and s[right].

Code

Here is the C++ code to accomplish the task:

#include <iostream>
#include <string>

std::string makeSmallestPalindrome(std::string s) {
    int n = s.length();
    int left = 0, right = n - 1;

    while (left < right) {
        if (s[left] != s[right]) {
            char minChar = std::min(s[left], s[right]);
            s[left] = s[right] = minChar;
        }
        left++;
        right--;
    }
    return s;
}

int main() {
    std::string s = "egcfe"; // Example input
    std::string result = makeSmallestPalindrome(s);
    std::cout << "Lexicographically smallest palindrome: " << result << std::endl;
    return 0;
}

Time Complexity

• O(n): We iterate through the string with two pointers, each making at most n/2 steps. Therefore, the time complexity is linear with respect to the length of the string.

• Space Complexity:

  • O(1): We modify the string in place, so no additional space proportional to the input size is needed apart from a few variables.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?