algoadvance

Leetcode 2697. Lexicographically Smallest Palindrome

Problem Statement

You are given a string s consisting of lowercase English letters, that can be rearranged to form a palindrome. Write a function that rearranges the input string s to form the lexicographically smallest palindrome.

Clarifying Questions

  1. Are there any constraints on the length of the input string s?
    • The problem does not specify, but feasibility usually implies a reasonable length such as n <= 10^5.
  2. Should we assume the input is always a rearrangement that can form a palindrome?
    • Yes, the problem states that s can be rearranged to form a palindrome.
  3. Do we need to return the string or modify it in place?
    • We need to return the lexicographically smallest palindrome as a new string.
  4. Are there any specific edge cases to consider?
    • Edge cases might include empty strings, single character strings, and strings where all characters are the same.

Strategy

To solve this problem, the approach is to construct a palindrome by considering the following facts:

  1. In a palindrome, the characters on the right half mirror those on the left half.
  2. To get the lexicographically smallest palindrome, use the smallest characters available for the first half and mirror them for the second half.

Steps:

  1. Count the frequency of each character in the string.
  2. Identify if there is at most one character with an odd frequency (it will be the center character for odd-length palindromes).
  3. Construct the first half of the palindrome using the characters in lexicographical order.
  4. Form the full palindrome by mirroring the first half and adding a center character if necessary.

Code

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class LexicographicallySmallestPalindrome {
    
    public String createSmallestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        
        Map<Character, Integer> charCount = new HashMap<>();
        for (char c : s.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }
        
        Character oddChar = null;
        int oddCount = 0;
        PriorityQueue<Character> minHeap = new PriorityQueue<>();
        
        for (Map.Entry<Character, Integer> entry : charCount.entrySet()) {
            char character = entry.getKey();
            int count = entry.getValue();
            if (count % 2 == 1) {
                oddCount++;
                oddChar = character;
            }
            minHeap.add(character);
        }
        
        if (oddCount > 1) {
            return ""; // This case shouldn't occur given the problem constraint
        }
        
        StringBuilder firstHalf = new StringBuilder();
        
        while (!minHeap.isEmpty()) {
            char character = minHeap.poll();
            int count = charCount.get(character);
            for (int i = 0; i < count / 2; i++) {
                firstHalf.append(character);
            }
        }
        
        String firstHalfStr = firstHalf.toString();
        StringBuilder secondHalf = new StringBuilder(firstHalfStr).reverse();
        
        if (oddChar != null) {
            return firstHalfStr + oddChar + secondHalf.toString();
        }
        
        return firstHalfStr + secondHalf.toString();
    }

    public static void main(String[] args) {
        LexicographicallySmallestPalindrome solution = new LexicographicallySmallestPalindrome();
        System.out.println(solution.createSmallestPalindrome("aabb")); // Should return "abba"
        System.out.println(solution.createSmallestPalindrome("aabbcc")); // Should return "abccba"
        System.out.println(solution.createSmallestPalindrome("racecar")); // Should return "aaccerrcaac"
        
    }
}

Time Complexity

Thus, the overall time complexity is O(n + k log k), where n is the length of the string and k is the number of distinct characters.

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