Show problems as
Classic problem #3517MediumStringSortingCounting Sort

Smallest Palindromic Rearrangement I

Real-world version: Smallest Mirror Word From The Same Beads
Tracked in this browser only
Read Smallest Palindromic Rearrangement I on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A bracelet is threaded with lettered beads, written out as the string s. The bracelet already reads the same forwards and backwards.

A jeweller is going to unthread every bead and thread them all back on in some order. The rethreaded bracelet must use exactly the beads that came off, all of them and nothing else, and it must again read the same forwards and backwards.

Of all the rethreadings that qualify, return the one that comes first alphabetically.

Examples

Example 1

Input
s = "dcabbacd"
Output
"abcddcba"

The beads are two each of a, b, c and d. The word `abcddcba` uses all eight of them and reads the same in both directions.

Example 2

Input
s = "cabac"
Output
"acbca"

There are two a, two c and a single b. The returned word reads the same in both directions and uses every bead.

Example 3

Input
s = "aabbaa"
Output
"aabbaa"

Four a beads and two b beads are already threaded in the alphabetically first qualifying order, so the bracelet comes back unchanged.

Example 4

Input
s = "cbabc"
Output
"bcacb"

Two b beads, two c beads and one a bead. The word `bcacb` uses all five and reads the same in both directions.

Constraints

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.
  • s reads the same forwards and backwards.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def smallest_mirror_word(beads: str) -> str:
Java
public String smallestMirrorWord(String beads)

More on the same topics