3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

String
Greedy
Counting
Sorting

TIME

O(26 * n)

SPACE

O(n)

Intuition

A palindrome is completely determined by its left half plus (for odd n) a single middle character:

P = L + mid + reverse(L)

A palindromic permutation of s exists only when at most one letter has an odd count, and that letter is forced to be mid. Everything else splits evenly, so L ranges over the permutations of the half-multiset count[c] // 2. Choosing L chooses P entirely.

Since the first h = n/2 characters of P are exactly L, comparing P to target splits into three cases against tpre = target[:h]:

L < tpre → P < target. Useless.
L > tpre → P > target already decided by the prefix, whatever the mirrored tail says. The smallest such P comes from the smallest such L.
L == tpre → the prefix ties, and the comparison falls through to mid + reverse(L) versus target[h:]. There is exactly one palindrome in this case, and if it clears target it beats every L > tpre candidate.

So check the tie case first, then fall back to "smallest permutation of the half-multiset strictly greater than tpre", which is exactly the sibling problem 3720 applied to the half.

Approach

Count letters of s. If more than one letter has an odd count (or the parity disagrees with n), no palindrome exists → "".
mid = the odd-count letter (empty for even n); half[c] = count[c] / 2; h = n / 2; tpre = target[:h].
Tie case: if tpre is exactly spellable from half (using all h slots), build P0 = tpre + mid + reverse(tpre). If P0 > target, return it, it is optimal.
Greedy case: find the smallest permutation L of half with L > tpre:
- Consume tpre greedily from half to get the longest matchable prefix.
- Walk p downward (returning characters to the pool), and at each p take the smallest available letter > tpre[p], then append the remaining letters in ascending order.
- A longer shared prefix always yields a smaller L, hence the descending search.
Return L + mid + reverse(L), or "" if no L exists.

Complexity

Time: O(26n), the greedy scans at most 26 letters per position, plus O(n) to assemble
Space: O(n), counts and the output string

Edge Cases

Two or more odd-count letters → no palindromic permutation at all (Example 3)
target is itself a palindromic permutation of s → the tie case produces P0 == target, which fails the strict test and correctly falls through (Example 1)
Largest palindromic permutation still <= target → "" (Example 2)
n == 1 → h == 0, L is empty, P is the single middle character
Only the first h characters drive the comparison unless L ties with tpre; the mirrored tail matters only in that one case

Code

class Solution:
    def smallestPalindrome(self, s: str, target: str) -> str:
        """
        3734. Lexicographically Smallest Palindromic Permutation Greater Than Target
        Time: O(26 * n)
        Space: O(n)
        """
        n = len(s)
        cnt = [0] * 26
        for ch in s:
            cnt[ord(ch) - 97] += 1

        # A palindrome needs at most one odd-count letter, matching n's parity.
        odd = [i for i in range(26) if cnt[i] % 2]
        if len(odd) > 1:
            return ""
        if (n % 2 == 0) != (len(odd) == 0):
            return ""
        mid = chr(97 + odd[0]) if odd else ""

        half = [c // 2 for c in cnt]
        h = n // 2
        tpre = target[:h]

        def build(left: str) -> str:
            return left + mid + left[::-1]

        # Case 1: the left half ties with target's prefix -> a single candidate.
        need = [0] * 26
        for ch in tpre:
            need[ord(ch) - 97] += 1
        if all(need[i] <= half[i] for i in range(26)):
            candidate = build(tpre)
            if candidate > target:
                return candidate

        # Case 2: smallest permutation of the half-multiset strictly above tpre.
        counts = half[:]
        matched = 0
        while matched < h and counts[ord(tpre[matched]) - 97] > 0:
            counts[ord(tpre[matched]) - 97] -= 1
            matched += 1

        # A longer shared prefix gives a smaller left half, so search downward.
        for p in range(matched, -1, -1):
            while matched > p:
                matched -= 1
                counts[ord(tpre[matched]) - 97] += 1
            if p >= h:
                continue
            for c in range(ord(tpre[p]) - 97 + 1, 26):
                if counts[c] > 0:
                    counts[c] -= 1
                    rest = "".join(chr(97 + j) * counts[j] for j in range(26))
                    return build(tpre[:p] + chr(97 + c) + rest)

        return ""

/**
 * 3734. Lexicographically Smallest Palindromic Permutation Greater Than Target
 * Time: O(26 * n)
 * Space: O(n)
 */
class Solution {
    private String mid = "";

    public String smallestPalindrome(String s, String target) {
        int n = s.length();
        int[] cnt = new int[26];
        for (int i = 0; i < n; i++) {
            cnt[s.charAt(i) - 'a']++;
        }

        // A palindrome needs at most one odd-count letter, matching n's parity.
        int oddCount = 0, oddIdx = -1;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] % 2 == 1) {
                oddCount++;
                oddIdx = i;
            }
        }
        if (oddCount > 1) {
            return "";
        }
        if ((n % 2 == 0) != (oddCount == 0)) {
            return "";
        }
        mid = (oddCount == 1) ? String.valueOf((char) ('a' + oddIdx)) : "";

        int[] half = new int[26];
        for (int i = 0; i < 26; i++) {
            half[i] = cnt[i] / 2;
        }
        int h = n / 2;
        String tpre = target.substring(0, h);

        // Case 1: the left half ties with target's prefix -> a single candidate.
        int[] need = new int[26];
        for (int i = 0; i < h; i++) {
            need[tpre.charAt(i) - 'a']++;
        }
        boolean spellable = true;
        for (int i = 0; i < 26; i++) {
            if (need[i] > half[i]) {
                spellable = false;
                break;
            }
        }
        if (spellable) {
            String candidate = build(tpre);
            if (candidate.compareTo(target) > 0) {
                return candidate;
            }
        }

        // Case 2: smallest permutation of the half-multiset strictly above tpre.
        int[] counts = half.clone();
        int matched = 0;
        while (matched < h && counts[tpre.charAt(matched) - 'a'] > 0) {
            counts[tpre.charAt(matched) - 'a']--;
            matched++;
        }

        // A longer shared prefix gives a smaller left half, so search downward.
        for (int p = matched; p >= 0; p--) {
            while (matched > p) {
                matched--;
                counts[tpre.charAt(matched) - 'a']++;
            }
            if (p >= h) {
                continue;
            }
            for (int c = tpre.charAt(p) - 'a' + 1; c < 26; c++) {
                if (counts[c] > 0) {
                    counts[c]--;
                    StringBuilder left = new StringBuilder();
                    left.append(tpre, 0, p);
                    left.append((char) ('a' + c));
                    for (int j = 0; j < 26; j++) {
                        for (int t = 0; t < counts[j]; t++) {
                            left.append((char) ('a' + j));
                        }
                    }
                    return build(left.toString());
                }
            }
        }

        return "";
    }

    private String build(String left) {
        return left + mid + new StringBuilder(left).reverse();
    }
}