413. Lexicographically Smallest Palindromic Permutation Greater Than Target

A palindrome is decided entirely by its first half, so ordering palindromes equals ordering their first halves. Build the smallest first half whose mirrored palindrome beats target: either reuse target's own prefix, or greedily break at the deepest position with the smallest larger letter.

Key observation: a palindrome is its first half

Group the letters of s. A permutation of s can be a palindrome only if at most one letter has an odd count — that letter (if any) must sit in the exact centre. If two or more letters have odd counts, no palindromic permutation exists, so return "".

Write n = len(s) and m = n // 2. Every palindrome looks like

[ first half (m letters) ] [ centre? ] [ reverse of the first half ]

The second half is forced to mirror the first, and the centre letter is fixed. So a palindromic permutation is completely determined by its first half, an arrangement of the half-multiset half[c] = cnt[c] / 2. Two palindromes compare in exactly the same order as their first halves (they first differ inside those m positions, or they are identical). We only ever need to build the first half.

Two ways to beat target

Let t = target[:m] be the slice of target that the first half lines up with. Compare a candidate first half h against t:

• If h > t, then the palindrome already exceeds target at that first differing position — the rest doesn't matter.
• If h < t, the palindrome is smaller than target. Useless.
• If h == t, the first m characters tie with target, so the winner is decided by the centre and the mirrored second half.

That gives two candidates, and we take the smaller valid palindrome:

Candidate B (tie the prefix). If t is itself a valid arrangement of the half-multiset, build pal = t + centre + reverse(t) and keep it only if pal > target. Because its first half equals t, this palindrome is smaller than any palindrome whose first half is strictly larger — so when it is valid, it wins.

Candidate A (break upward). Find the lexicographically smallest first half, drawn from the half-multiset, that is strictly greater than t:

1. Reuse t's letters as a prefix for as long as the pool still contains them.
2. At the deepest position i where the pool holds a letter strictly greater than t[i], place the smallest such letter, then empty the remaining pool in ascending order for the smallest possible tail.
3. Mirror this half into a full palindrome. It automatically exceeds target.

The answer is the smaller of the two candidate palindromes that exist; if neither exists, return "".

Worked example: s = "baba", target = "abba"

Counts: a:2, b:2 — no odd counts, so a palindrome is possible. m = 2, half = {a:1, b:1}, no centre. t = target[:2] = "ab".

• Candidate B: "ab" is a valid arrangement of {a,b}. Palindrome = "ab" + "" + "ba" = "abba". But "abba" > "abba" is false (they're equal), so B is rejected.
• Candidate A: find the smallest half > "ab".
  • Position 0: pool {a,b} has b > 'a' — record a break "b" + tail("a") = "ba". Then reuse t[0]='a', pool becomes {b}.
  • Position 1: pool {b} has nothing > 'b'. Reuse t[1]='b', pool empties.
  • The deepest recorded break is "ba". Mirror it: "ba" + "" + "ab" = "baab".
• Only Candidate A survives, so the answer is "baab".

A case where the centre matters: s = "aac", target = "abb"

Counts a:2, c:1; c is the single odd letter, so centre = 'c'. m = 1, half = {a:1}, t = "a". Candidate B: "a" is a valid half, palindrome = "a" + "c" + "a" = "aca", and "aca" > "abb" (they first differ at index 1: c > b). B is valid, so the answer is "aca".

Complexity

• Time: O(n + m·26) = O(n·26). Counting letters is O(n); the greedy scans each of the m positions against at most 26 letters and builds the tail once.
• Space: O(n) for the constructed half and palindrome (the count arrays are O(26)).

class Solution {
    public String lexPalindromicPermutation(String s, String target) {
        int n = s.length();
        int[] cnt = new int[26];
        for (int k = 0; k < n; k++) cnt[s.charAt(k) - 'a']++;

        // A palindrome allows at most one odd-count letter (the centre).
        int oddCount = 0, oddChar = -1;
        for (int c = 0; c < 26; c++) {
            if (cnt[c] % 2 == 1) { oddCount++; oddChar = c; }
        }
        String middle;
        if (n % 2 == 0) {
            if (oddCount != 0) return "";
            middle = "";
        } else {
            if (oddCount != 1) return "";
            middle = String.valueOf((char) ('a' + oddChar));
        }

        // A palindrome is fully determined by its first half (length m); ordering
        // palindromes matches ordering their first halves, so we build the half.
        int m = n / 2;
        int[] half = new int[26];
        for (int c = 0; c < 26; c++) half[c] = cnt[c] / 2;
        String t = target.substring(0, m);

        String best = null;

        // Candidate B: keep the first half exactly equal to target's prefix when
        // that prefix is a valid arrangement of the half-multiset.
        int[] tc = new int[26];
        for (int k = 0; k < t.length(); k++) tc[t.charAt(k) - 'a']++;
        boolean formable = true;
        for (int c = 0; c < 26; c++) if (tc[c] != half[c]) { formable = false; break; }
        if (formable) {
            String pal = t + middle + new StringBuilder(t).reverse();
            if (pal.compareTo(target) > 0) best = pal;
        }

        // Candidate A: smallest first half from the multiset strictly greater
        // than t. Reuse t's prefix as far as the pool allows, then break at the
        // deepest position with the smallest greater letter and sort the tail.
        int[] remaining = half.clone();
        StringBuilder prefix = new StringBuilder();
        String cand = null;
        for (int i = 0; i < m; i++) {
            int ti = t.charAt(i) - 'a';
            int chosen = -1;
            for (int c = ti + 1; c < 26; c++) {
                if (remaining[c] > 0) { chosen = c; break; }
            }
            if (chosen != -1) {
                int[] rem = remaining.clone();
                rem[chosen]--;
                StringBuilder sb = new StringBuilder(prefix);
                sb.append((char) ('a' + chosen));
                for (int c = 0; c < 26; c++)
                    for (int r = 0; r < rem[c]; r++) sb.append((char) ('a' + c));
                cand = sb.toString();
            }
            if (remaining[ti] > 0) {
                remaining[ti]--;
                prefix.append(t.charAt(i));
            } else {
                break;
            }
        }
        if (cand != null) {
            String palA = cand + middle + new StringBuilder(cand).reverse();
            if (best == null || palA.compareTo(best) < 0) best = palA;
        }

        return best == null ? "" : best;
    }
}