0

Smallest palindrome from a symmetric string's letters

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Smallest palindrome from a symmetric string's letters

Companies: Amazon

Difficulty: Medium

Problem statement

You are given a string s of lowercase English letters that is already a palindrome. Rearrange all of its characters to form a new palindrome, and return the one that comes first in dictionary (lexicographic) order.

Implement:

def smallest_palindrome(s: str) -> str: ...

If the input turns out not to allow any palindrome, return the empty string.

Constraints

  • 1 <= len(s) <= 10^5
  • s contains only 'a' to 'z'.

Example 1

Input:  s = "cbabc"
Output: "bcacb"

The letters are two b, two c and one a. The a must sit in the middle, and putting b before c on the left gives the smallest result.

Example 2

Input:  s = "daccad"
Output: "acddca"

Every letter appears an even number of times, so there is no middle character.

Approach

A palindrome is fixed by its first half and, for odd length, its middle
character. The second half is the mirror of the first. So the question is
really: what is the smallest possible first half?

Brute force. Generate every distinct permutation of s, keep the
palindromes, and return the minimum. This is O(n! · n) and only works for
tiny inputs. It is still worth naming, because it states the goal plainly
and gives you an oracle to test against.

Optimal: count, sort the half, mirror.

  1. Count each letter. A palindrome exists only if at most one letter has an
    odd count. The input is symmetric, so this holds, but checking costs
    nothing and makes the function safe for any input.
  2. Each letter c contributes count[c] // 2 copies to the left half. The
    letter with the odd count, if there is one, becomes the middle.
  3. Write the left half in ascending order, then the middle, then the left
    half reversed.

Why this is the smallest. Two palindromes of the same length are
compared position by position. The first difference between them is always
in the left half or the middle, because the right half is fixed by the left
half. The multiset of letters in the left half is forced: it is exactly
count[c] // 2 of each letter. The middle letter is forced too. Among all
orderings of a fixed multiset, the sorted one is the smallest. So the
sorted left half gives the smallest palindrome, and there is no choice left
to make.

Invariants. The left half holds exactly half (rounded down) of every
letter. At most one letter is left over, and it goes in the middle. Because
the alphabet is 26 letters, a counting sort replaces a comparison sort and
the whole method is linear.

Code

from collections import Counter
from itertools import permutations


def smallest_palindrome(s: str) -> str:
    """Return the lexicographically smallest palindrome that uses every
    character of s exactly once. Return "" if no palindrome is possible."""
    counts = [0] * 26
    for ch in s:
        counts[ord(ch) - ord("a")] += 1

    middle = ""
    left_parts: list[str] = []
    for i, c in enumerate(counts):
        letter = chr(ord("a") + i)
        if c % 2 == 1:
            if middle:  # a second odd count: no palindrome exists
                return ""
            middle = letter
        left_parts.append(letter * (c // 2))  # ascending order by construction

    left = "".join(left_parts)
    return left + middle + left[::-1]


def smallest_palindrome_brute(s: str) -> str:
    """Oracle for small inputs: try every arrangement."""
    best = ""
    for p in set(permutations(s)):
        cand = "".join(p)
        if cand == cand[::-1] and (not best or cand < best):
            best = cand
    return best


if __name__ == "__main__":
    assert smallest_palindrome("z") == "z"
    assert smallest_palindrome("bab") == "bab"
    assert smallest_palindrome("babab") == "abbba"
    assert smallest_palindrome("daccad") == "acddca"
    assert smallest_palindrome("cbabc") == "bcacb"
    assert smallest_palindrome("aabb") == "abba"
    assert smallest_palindrome("abc") == ""
    assert smallest_palindrome("a" * 100_000) == "a" * 100_000

    import random
    for _ in range(300):
        n = random.randint(1, 7)
        half = "".join(random.choice("abc") for _ in range(n // 2))
        mid = random.choice("abc") if n % 2 else ""
        pal = half + mid + half[::-1]
        assert smallest_palindrome(pal) == smallest_palindrome_brute(pal), pal
    print("ok")

Complexity

  • Time: O(n + σ), where σ = 26 is the alphabet size. One pass to count,
    one pass over the alphabet, and O(n) to build the output.
  • Space: O(σ) for the counts plus O(n) for the output string.
  • The brute force is O(n! · n) time and is only an oracle for tests.

Test cases

  • "z" → "z" (single character).
  • "bab" → "bab" (already the smallest; a is the only odd count).
  • "babab" → "abbba" (b appears 3 times, so it takes the middle).
  • "daccad" → "acddca" (even length, no middle).
  • "cbabc" → "bcacb".
  • "aabb" → "abba".
  • "abc" → "" (three odd counts; only possible if the input is not
    symmetric, so this tests the guard).
  • "a" * 100000 → the same string (largest input, one letter).
  • Random palindromes up to length 7 match the brute-force oracle.

Follow-ups

  1. Input may not be a palindrome. Return "" (or -1) when more than
    one letter has an odd count. The code already does this.
  2. The k-th smallest palindromic arrangement. The middle is still fixed,
    so you need the k-th distinct permutation of the left-half multiset.
    Build it one position at a time: for each candidate letter, count the
    permutations of what remains with the multinomial
    m! / ∏ cnt[c]!; skip whole blocks while k is larger, otherwise fix the
    letter. Cap the counts at k to avoid huge numbers. Return "" if fewer
    than k arrangements exist.
  3. Change characters instead of rearranging. With the fewest
    replacements, make s a palindrome and keep it smallest. Use two
    pointers from both ends and set each mismatched pair to the smaller of
    the two letters. O(n).
  4. Larger alphabet (Unicode). Replace the 26-slot array with a hash map
    and sort its keys: O(n + σ log σ) where σ is the number of distinct
    characters.
  5. Largest palindrome, or a fixed middle. Iterate the alphabet in
    descending order for the largest. If the interviewer requires a given
    character in the middle, check that its count is odd and every other
    count is even.

Interviewer expectations

Mid-level (L4)

  • Sees that the right half mirrors the left, so only the left half matters.
  • Writes the count / sorted half / mirror solution without bugs, including
    odd and even lengths.
  • States O(n) time and handles a single-character input.

Senior (L5)

  • Explains why the sorted half is optimal (the half's letters are forced,
    and the sorted order of a fixed multiset is the smallest).
  • Uses a counting sort, not sorted(s), and notes the 26-letter bound.
  • Validates the input anyway and tests against a brute-force oracle.
  • Handles the k-th arrangement follow-up with multinomial counting.

Staff (L6+)

  • Moves quickly through the base case and frames the family of variants
    (rearrange vs. replace, smallest vs. k-th, any alphabet).
  • Discusses overflow in the k-th variant and caps counts at k.
  • Talks about API design: what to return when no palindrome exists, and
    how to make the function safe for untrusted input.

Sign in to comment, vote or remix.