3734. Lexicographically Smallest Palindromic Permutation Greater Than Target
Difficulty: Hard | Published on August 28, 2026
Let's build this up from zero. This is a Hard problem, so we'll go slow and steady.
1. Problem in Very Simple Language
You are given two words, INLINECODE0 and INLINECODE1, both made of only lowercase letters, and both the same length.
You are allowed to rearrange the letters of INLINECODE2 in any order you like (this is called a "permutation" — just a fancy word for "a rearrangement using the exact same letters, same amount of each").
Among all the rearrangements of INLINECODE3 that are palindromes (words that read the same forwards and backwards, like "level" or "baab"), you must find the one that:
is strictly greater than INLINECODE4 when compared like dictionary words, and is the smallest one that satisfies that condition.
If no rearrangement of INLINECODE5 is even a palindrome, or none of the palindromic rearrangements beats INLINECODE6, you return an empty string INLINECODE7.
What's given: INLINECODE8 (letters you're allowed to use), INLINECODE9 (the word you must beat). What to find: the smallest palindrome word, built only from INLINECODE10's letters, that is bigger than INLINECODE11. What to return: that word, or INLINECODE12 if impossible.
2. Real-Life Analogy
Imagine you have a bag of Scrabble tiles — say two INLINECODE13s and two INLINECODE14s. You're told: "Arrange all these tiles in a row so the row reads the same from left to right and right to left (a palindrome), and make sure your row, read as a word, comes after the word INLINECODE15 in the dictionary — but choose the arrangement that is the closest possible word after it, not some huge jump."
You can't just grab any arrangement — it must (a) use every tile exactly once, (b) be a palindrome, and (c) be the smallest dictionary word that still beats the target word.
3. Important Programming Concepts I Need First
String
Concept: A string is just a sequence of characters, like a row of tiles, each with a position number starting at 0. Example: INLINECODE16 has INLINECODE17 at position 0, INLINECODE18 at position 1, INLINECODE19 at position 2, INLINECODE20 at position 3. Why we need it: Both INLINECODE21 and INLINECODE22 are strings, and our answer is a string too.Array (specifically, a frequency array)
Concept: An array is a numbered list of boxes. A "frequency array" of size 26 has one box per letter of the alphabet, and each box holds a count. Example: For INLINECODE23, box for INLINECODE24 = 2, box for INLINECODE25 = 2, everything else = 0. Why we need it: We need to know exactly how many of each letter we have available, since we must use every letter of INLINECODE26 exactly once.Loop
Concept: A loop repeats an action for each item in a list, without you writing the same line 300 times by hand. Example: "For every letter in INLINECODE27, add 1 to that letter's counting box." Why we need it: We scan through strings and arrays constantly (counting letters, comparing positions, etc.).If/else
Concept: A way of telling the program "do this if a condition is true, otherwise do that." Example: "If the current letter is bigger than the target's letter, we found our answer." Why we need it: The entire trick of "find the smallest letter bigger than target's letter" is one big if/else decision repeated many times.Palindrome
Concept: A word that reads identically forwards and backwards. Position INLINECODE28 from the start must equal position INLINECODE29 from the end. Example: INLINECODE30 — first letter INLINECODE31 = last letter INLINECODE32; second letter INLINECODE33 = second-to-last letter INLINECODE34. Why we need it: Our answer must be a palindrome, which cuts our freedom in half — we only get to choose the first half of the letters; the second half is forced to mirror it.HashMap / frequency counting (same idea as the frequency array above, just conceptually)
Concept: A way to quickly look up "how many of X do I have left?" Why we need it: As we build our answer letter by letter, we constantly need to ask "do I still have a INLINECODE35 left to use?"Greedy Algorithm
Concept: A greedy algorithm makes the best-looking choice at each step, one step at a time, hoping (and in this case, proving) it leads to the overall best answer. Example: To find the smallest number bigger than 47 using digits {1,7,9}, you try to keep the first digit as "4-like" as possible, only bumping a digit up when forced to. Why we need it: We build our palindrome by matching INLINECODE36 as long as possible, then bumping the very next letter up just enough — that's a greedy strategy.Comparing strings ("lexicographic" order)
Concept: Comparing two strings works like comparing words in a dictionary: look at the first position where they differ; whichever has the smaller letter there is the smaller string. Example: INLINECODE37 vs INLINECODE38 — first letters INLINECODE39 vs INLINECODE40 — since INLINECODE41, INLINECODE42. Why we need it: The entire goal ("smallest palindrome greater than target") is defined using this comparison rule.Time Complexity (Big-O)
Concept: A way of describing "roughly how much work does my program do as the input grows," ignoring small constant details. Why we need it: With INLINECODE43 up to 300, we need to make sure our solution isn't doing something silly like checking every possible arrangement (which would be astronomically slow).4. Understand the Input
Take Example 1: CODEBLOCK0
INLINECODE44 tells us: we have exactly these 4 letters to use, in some order: INLINECODE45 → that's two INLINECODE46s and two INLINECODE47s. We are not stuck with the order INLINECODE48 — we can rearrange freely. INLINECODE49 is the word we must beat. It happens to already be a palindrome itself, but that's not required of INLINECODE50 — it's just the "line in the sand" we must cross. We are looking for: a rearrangement of INLINECODE51 that (1) is a palindrome, and (2) is the smallest one that is strictly bigger than INLINECODE52. INLINECODE53 and INLINECODE54-style "important numbers" don't apply here (that was the Two Sum example from your template) — instead, the important thing is the counts: 2 INLINECODE55s and 2 INLINECODE56s. Since both counts are even, a palindrome is possible (every letter needs a "partner" on the other side, except possibly one letter in the very middle if the word length is odd).
5. Understand the Output
Output: INLINECODE57
All palindromic rearrangements of INLINECODE58, sorted like a dictionary, are: INLINECODE59, INLINECODE60. (Only two exist, because once you decide the first half of a palindrome, the second half is forced.) INLINECODE61 is not strictly greater than INLINECODE62 — it's equal, and we need strictly greater. INLINECODE63 is strictly greater than INLINECODE64 (compare first letters: INLINECODE65). Since INLINECODE66 is the only remaining candidate and it works, it's the answer.
6. Solve the Example Manually
Let's solve Example 1 by hand, the way a human would, without writing any code.
We have letters INLINECODE67 and INLINECODE68.
Since the answer must be a 4-letter palindrome, only the first 2 letters are really "ours to choose" — the last 2 letters are forced to mirror the first 2.
| Step | What I try for first half | Full palindrome | Compare to target "abba" | Result |
|---|---|---|---|---|
| 1 | "aa" (smallest possible) | "aaaa" — wait, we don't have 4 INLINECODE69s, only 2. Not a valid rearrangement using our letters (need to use exactly 2 a's and 2 b's) | — | invalid, skip |
| 2 | "ab" | "ab" + reverse("ab") = "abba" | equal to target, not strictly greater | fails |
| 3 | "ba" | "ba" + reverse("ba") = "baab" | "baab" > "abba"? First letters: b > a → yes | This works! |
7. Think Like a Programmer
Let's turn that manual process into logic.
What do I know? I know exactly which letters I'm allowed to use (their counts), and I know the target string I must beat. What do I need to find? The smallest palindrome, built from those letters, greater than target. What can I try? Since the answer is a palindrome, I only need to decide the first half of it — the rest is automatic (mirrored). If the length is odd, there's one middle letter too, but that middle letter is not free — only one letter in the whole alphabet is allowed to appear an odd number of times, and it MUST be that one, sitting exactly in the middle. No choice there. What happens if I try every possibility? I could generate every arrangement of the first half, build the palindrome, and compare to target — but with up to 150 letters in that first half, the number of arrangements is unimaginably huge. Too slow. Can I make it faster? Yes — just like finding "the smallest number bigger than 472 using certain digits," I don't need to generate every option. I can be smart: try to match INLINECODE73 letter-by-letter for as long as possible, then at the very last moment I'm forced to change something, put the smallest legal letter that's bigger than target's letter there, and fill everything after that with the smallest possible letters. What information should I remember? How many of each letter I still have left to place, as I place letters one at a time. What pattern do I notice? The longer I can match INLINECODE74 exactly before being forced to increase a letter, the smaller (closer to target) my final answer will be. So I want to match as long as possible, then bump the last possible position, not an early one.
8. Start With the Brute Force Solution
Brute force idea: Generate every distinct permutation of INLINECODE75, keep only the ones that are palindromes, sort them, and pick the smallest one that's bigger than INLINECODE76.
Why it works: It's literally trying everything, so it can't miss the answer.
Why it's correct: By definition, checking every single arrangement guarantees we find the true smallest valid one.
Time complexity: Generating all permutations of a string of length INLINECODE77 takes about INLINECODE78 (n factorial) time — for INLINECODE79, this number has hundreds of digits. Completely impossible to run.
Space complexity: Also astronomical, since we'd try to store or generate all these permutations.
We won't even write this code for real — it's only useful as a mental starting point, since actually running it would never finish. But conceptually:
CODEBLOCK1
9. Explain the Brute Force Code Line by Line
INLINECODE80 — imagine a function that produces every possible reordering of the letters in INLINECODE81. For INLINECODE82 that would include INLINECODE83, INLINECODE84, INLINECODE85, INLINECODE86, INLINECODE87, INLINECODE88, etc. INLINECODE89 — checks whether a string reads the same forwards and backwards, by comparing position INLINECODE90 with position INLINECODE91 for every INLINECODE92. INLINECODE93 — puts the palindromic permutations in dictionary order, smallest first. The final INLINECODE94 loop — walks through the sorted list and returns the very first one that beats INLINECODE95, since that's guaranteed to be the smallest one that does.
10. Why Is the Brute Force Solution Not Ideal?
Imagine INLINECODE96 has 300 letters. The number of ways to arrange 300 items is a number so large it has around 600+ digits — more than the number of atoms in the observable universe, many times over. No computer, now or in the future, could generate even a tiny fraction of that list. We need a method that builds the answer directly, without ever listing "all the other options."
11. Find the Better Approach
"Can we avoid doing unnecessary work?"
Yes. Two key realizations shrink the problem enormously:
1. We never need to consider the second half of the palindrome as a free choice. It's 100% determined by the first half (mirrored). So instead of deciding INLINECODE97 letters, we only decide about INLINECODE98 letters. 2. We don't need to generate every arrangement of that first half either. We can build it directly, matching INLINECODE99 as long as possible, the same way you'd figure out "what's the next number after 4729 using only these digits" without listing every number.
CODEBLOCK2
12. Key Insight
Before the insight
We were thinking about the whole INLINECODE100-letter string as something we need to search through many possible full arrangements of.The problem
A palindrome's second half isn't independent — it's a mirror of the first half — but naive brute force ignored that free lunch and searched the whole space anyway.The insight
Once you fix the first half of a palindrome, the whole string is fixed. So the entire problem shrinks to: find the smallest valid first-half string such that, once mirrored into a full palindrome, it beats INLINECODE101. And finding "the smallest string beating a target, letter-budget-limited" is a classic pattern: match the target as long as possible, then at the first position where you're forced to deviate, place the smallest available letter that's bigger than target's letter there, and fill everything after with the smallest leftover letters.There's one more twist: if the string length is odd, exactly one letter is allowed to appear an odd number of times in INLINECODE102 — and that letter is
forced to sit in the very middle. You never get to choose it.After the insight
Instead of touching all INLINECODE103 letters freely, we only ever make decisions about the first INLINECODE104 (rounded down) letters. We scan left to right, trying to match INLINECODE105, and the moment we can't match anymore (or matching all the way turns out to not be enough), we bump the letter at that position up to the smallest legal option greater than target's letter, then fill the rest smallest-first. This takes roughly one pass through the string — extremely fast.13. Dry Run the Optimized Solution
Let's dry-run Example 1 again, but now the "smart" way, tracking our leftover letter budget.
INLINECODE106 → counts: INLINECODE107. Length INLINECODE108 is even, so half = 2, no middle letter. Since we only place each letter once in the first half but it represents 2 copies in the full word, our "half budget" is INLINECODE109 (half of each count).
INLINECODE110.
| Step | Position | Target letter | Budget before | Try to match target exactly? | What happens |
|---|---|---|---|---|---|
| 1 | 0 | INLINECODE111 | INLINECODE112 | Yes, we have an INLINECODE113 | Use it. Budget → INLINECODE114 |
| 2 | 1 | INLINECODE115 | INLINECODE116 | Yes, we have a INLINECODE117 | Use it. Budget → INLINECODE118 |
Since exact matching failed, we back up one position and try to bump it:
| Step | Position | Give back letter | Budget now | Look for a letter > target letter | Result |
|---|---|---|---|---|---|
| 3 | 1 (give back INLINECODE123 used at step 2) | INLINECODE124 | INLINECODE125 | Need something > INLINECODE126 — nothing (no INLINECODE127, etc. available) | Fails at position 1 |
| 4 | 0 (give back INLINECODE128 used at step 1) | INLINECODE129 | INLINECODE130 | Need something > INLINECODE131 — we have INLINECODE132! | Use INLINECODE133 here |
This matches our manual answer from Section 6! 🎉
14. Optimized Code
CODEBLOCK3
CODEBLOCK4
15. Explain Optimized Code Line by Line
INLINECODE139 — one box per letter, all start at 0. We'll count how many INLINECODE140s, INLINECODE141s, ... INLINECODE142 has. The INLINECODE143 loop right after — walks through every letter of INLINECODE144 once, incrementing its box. After this, INLINECODE145 tells you exactly how many INLINECODE146s exist in INLINECODE147. INLINECODE148 / INLINECODE149 — we scan all 26 boxes; if a letter's count is odd, a palindrome needs it to sit alone in the middle. There can be at most one such letter, or a palindrome is impossible. INLINECODE150 — 1 if the target length is odd (there's a middle seat), 0 if even (no middle seat). The two INLINECODE151 checks right after — this is the "is a palindrome even possible" gate. If length is even but some letter has an odd count, impossible. If length is odd but there isn't exactly one odd-count letter, impossible. INLINECODE152 — how many letters we get to freely decide (the first half). INLINECODE153 — since each letter in the first half is mirrored once in the second half, we only get half as many "free placements" as the full count. INLINECODE154 — the forced middle letter, if any. Notice: this is not a choice — there can only be one candidate. The INLINECODE155 loop — this is us trying to copy INLINECODE156's first half exactly, one letter at a time, spending from our budget as we go, stopping the instant we run out of the needed letter. The INLINECODE157 block — if we successfully copied the entire first half, our string so far exactly equals INLINECODE158's first half. Now we must check: does the forced rest of the string (center letter + mirrored tail) already make our full string bigger than INLINECODE159? We check the center first (if it exists), then the tail. If yes, we return immediately — this is the smallest possible answer, since we matched INLINECODE160 as long as humanly possible. If that check fails (equal or smaller), we don't give up — we go back and try increasing some earlier letter instead. INLINECODE161 — this "gives back" the last letter we tentatively used, since we're now allowed to try something different there instead of matching target exactly. The main INLINECODE162 loop — this is the heart of the "bump the letter" logic. At each position, we look through our remaining budget for the smallest letter bigger than target's letter at that position (INLINECODE163). If we find one (INLINECODE164), we use it, then fill everything after with the smallest leftover letters (since nothing more needs comparing — we've already guaranteed we're bigger than target). Then we mirror to build the full palindrome and return. If we don't find one, we "give back" the letter target had at the previous position (so we can try bumping there instead) and move one position to the left — this is exactly like carrying in addition, but for letters. If we run out of positions entirely, no valid palindrome beats INLINECODE165, so we return INLINECODE166.16. Test With Multiple Examples
Example 1 — Normal Case
Input: INLINECODE167 → dry-ran above → Output: INLINECODE168 ✔️Example 2 — Different Case (exact prefix match, but tail is equal, and no bump possible)
Input: INLINECODE169. Budget: INLINECODE170. Matching target's first letter INLINECODE171: budget has INLINECODE172, use it, budget → INLINECODE173. Second letter INLINECODE174: budget has no INLINECODE175 left — matching stops at INLINECODE176. We try to bump position 1 (target letter INLINECODE177): need something INLINECODE178 in INLINECODE179 — nothing. Give back target[0]=INLINECODE180 → budget INLINECODE181. Try to bump position 0 (target letter INLINECODE182): need INLINECODE183 — nothing (INLINECODE184 is not bigger). No position works → Output: INLINECODE185 ✔️Example 3 — Edge Case (palindrome impossible at all)
Input: INLINECODE186. Counts: INLINECODE187 — three odd counts. Since length 3 is odd, we need exactly one odd count, not three → impossible → Output: INLINECODE188 ✔️17. Edge Cases
Palindrome is impossible from the start (wrong number of odd-count letters) → return INLINECODE189 immediately, no need to even look at INLINECODE190. Every rearrangement is smaller than or equal to INLINECODE191 → our search runs out of positions to bump → return INLINECODE192. The only valid palindrome exactly equals INLINECODE193 → since we need strictly greater, this doesn't count, and we must look for something else (or fail). INLINECODE194's letters can't even be matched at position 0 (e.g., target starts with INLINECODE195 but our budget has no letter ≥ that) → the "bump" search starts right at position 0 and likely fails fast. All letters identical (e.g., INLINECODE196) → only one palindrome exists (INLINECODE197); either it beats target or it doesn't. Odd length, only one letter total (INLINECODE198) → INLINECODE199, the entire string is just the center letter — no real search needed, just compare directly.18. Time Complexity
What is time complexity? It's a way of estimating how the
amount of work grows as the input grows, without worrying about exact seconds — like saying "doubling my grocery list roughly doubles my shopping time," rather than measuring it with a stopwatch.CODEBLOCK5
Why: We compute letter counts in one pass (INLINECODE200). We try to match target's first half in one pass (INLINECODE201). In the worst case, our "bump" search walks backward through the first half once (INLINECODE202), and at each position checks up to 26 letters (INLINECODE203), which is a constant, not something that grows with INLINECODE204. Building the final answer string is another single pass. All together, this is proportional to INLINECODE205, not to some huge exploding number — like sorting your grocery list once instead of trying every possible order of it.
19. Space Complexity
We use a few fixed-size arrays of length 26 (letter counts, half-budget, etc.) — this doesn't grow with INLINECODE206 at all, it's always 26 boxes. We build the answer string, which is length INLINECODE207.So extra memory used is INLINECODE208 (mostly just for building and returning the answer itself), plus a small constant INLINECODE209 for our counting arrays.
20. Common Mistakes Beginners Make
❌ "I should just sort the letters and check if that's a palindrome." ✅ Sorting only gives you
one arrangement — usually not even a palindrome, and definitely not necessarily the smallest one greater than target. You need to specifically construct a palindrome by mirroring a chosen first half.❌ "The middle letter (for odd length) is something I get to pick to help beat target." ✅ The middle letter is completely forced — there's only ever at most one letter with an odd count, and it
must be the center. You never get to choose it.❌ "I should compare my constructed string to target only up to the half-way point, since after that it's just a mirror anyway." ✅ You must compare the
entire string, because even though the second half is a mirror, it can still be the exact part that decides whether your string is bigger or smaller than target (see how the tail check mattered in Example 2's dry run).❌ "Once I find any position where I can place a bigger letter, that's the answer." ✅ You must search from the rightmost possible position backward, because bumping a letter as late as possible keeps your answer as close (and thus as small) as possible while still being greater than target.
21. How to Recognize This Pattern in Other Problems
If you see phrasing like this, think "match-as-long-as-possible, then bump the smallest legal amount":
CODEBLOCK6
22. Interview Thinking
CODEBLOCK7
Applied here: this is exactly the path we walked — brute force → realize the mirror trick → realize it's a "match then bump" construction problem → handle the tricky "exact match, check the tail" case → land on an INLINECODE210 solution.
23. Mini Challenge
Before we wrap up, try answering these in your head (or on paper):
1. If INLINECODE211 and INLINECODE212, what's the half-budget (INLINECODE213 and INLINECODE214 counts for the first half)? 2. At position 0, target's letter is INLINECODE215. Do we try to match it first, or immediately look for something bigger? 3. Suppose we match the
entire* first half exactly to target, and the mirrored tail comes out smaller than target's real tail. What should we do next?Answer to Mini Challenge
1. Full counts: INLINECODE216. Half-budget: INLINECODE217. 2. We always try to match first — matching keeps our answer as close to (and thus as small as) possible while beating target; we only "bump" when matching is no longer possible or doesn't work out. 3. If the mirrored tail turns out smaller (or equal), the exact-match candidate fails to beat target, so we go back and search backward from the last matched position, looking for the rightmost spot where we can legally place a letter bigger than target's letter there.
24. Final Revision
🧠 Problem in One Sentence
Build the smallest palindrome, using exactly the letters of INLINECODE218, that is strictly bigger than INLINECODE219.🔑 Main Idea
A palindrome's second half is just a mirror of its first half, so we only ever need to construct the first half — and we build that first half by matching INLINECODE220 as long as possible, then bumping the letter at the latest possible position up to the smallest legal larger option.⚙️ Algorithm
1. Count letters of INLINECODE221; check a palindrome is even possible (at most one odd-count letter). 2. Compute the "half budget" (each count divided by 2) and the forced center letter, if any. 3. Try to match INLINECODE222's first half exactly using the budget. 4. If fully matched, check the forced center + mirrored tail — if that already beats target, return it (smallest possible answer). 5. Otherwise, search backward for the rightmost position where a bigger letter can be placed; place it, fill the rest with the smallest leftover letters, mirror, and return. 6. If nothing works anywhere, return INLINECODE223.⏱️ Complexity
Time: INLINECODE224 Space: INLINECODE225 (for the answer string; counting arrays are a constant O(26))🎯 Pattern to Remember
"Match-then-bump" construction, combined with "a palindrome is only half-free."25. Beginner Quiz
1. (Understanding) In your own words, why can't we just pick any palindrome permutation of INLINECODE226 — what two conditions must our answer satisfy? 2. (Basic concept) If INLINECODE227, what would the "half-budget" array contain (just for letters INLINECODE228 and INLINECODE229)? 3. (Logic) Why do we search for the position to "bump" starting from the end of the matched prefix and moving backward, rather than starting from position 0 and moving forward? 4. (Dry run) For INLINECODE230 and INLINECODE231, walk through: what's the half-budget, does the first half match target exactly, and if not, what's the final answer? 5. (Complexity/pattern) Why is this solution INLINECODE232 instead of something like INLINECODE233 or INLINECODE234, and what "signal words" in a problem statement should make you think of this match-then-bump technique in the future?
Take your time — send me your answers whenever you're ready, and I'll walk through them with you!