3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

class Solution {
    public String lexPalindromicPermutation(String s, String target) {
        int n = s.length();
        int[] freq = new int[26];
        for (char c : s.toCharArray()) freq[c - 'a']++;

        // Palindrome possible only if at most 1 odd frequency
        int oddCount = 0;
        for (int f : freq) if (f % 2 != 0) oddCount++;
        if (oddCount > 1) return "";

        // Middle character for odd length
        char mid = 0;
        for (int i = 0; i < 26; i++)
            if (freq[i] % 2 != 0) { mid = (char) ('a' + i); break; }

        int halfLen = n / 2;

        // Build smallest left half
        char[] smallestHalf = buildSmallestHalf(freq, halfLen);
        String smallest = buildPalindrome(smallestHalf, mid, n);
        if (smallest.compareTo(target) > 0) return smallest;

        // target's left half (first halfLen chars)
        char[] tHalf = target.substring(0, halfLen).toCharArray();

        // We'll try to build left half that makes palindrome > target
        // Key insight: palindrome P > target T iff
        //   leftHalf > tHalf  OR
        //   (leftHalf == tHalf AND mid part makes it greater — only possible
        //    when n is odd AND mid > target[halfLen])
        
        // Strategy: go position by position, try to match tHalf greedily
        // At each pos, either:
        //   - place same char as tHalf[pos] and continue (greedy match)
        //   - place char > tHalf[pos] and fill rest with smallest → candidate
        // Also check: if we matched entire tHalf, check mid character case

        int[] avail = new int[26];
        for (int i = 0; i < 26; i++) avail[i] = freq[i] / 2;

        char[] builtHalf = new char[halfLen];
        String bestCandidate = null;

        for (int pos = 0; pos < halfLen; pos++) {
            int tChar = tHalf[pos] - 'a';

            // Option A: place char > tHalf[pos] at this pos, fill rest smallest
            for (int c = tChar + 1; c < 26; c++) {
                if (avail[c] > 0) {
                    // Use char c at pos
                    avail[c]--;
                    builtHalf[pos] = (char) ('a' + c);

                    // Fill rest with smallest
                    int[] tempAvail = avail.clone();
                    char[] tempHalf = builtHalf.clone();
                    int fill = pos + 1;
                    for (int cc = 0; cc < 26; cc++)
                        for (int j = 0; j < tempAvail[cc]; j++)
                            if (fill < halfLen) tempHalf[fill++] = (char) ('a' + cc);

                    String candidate = buildPalindrome(tempHalf, mid, n);
                    if (bestCandidate == null || candidate.compareTo(bestCandidate) < 0)
                        bestCandidate = candidate;

                    // Restore
                    avail[c]++;
                    break; // smallest such c is best, no need to try larger
                }
            }

            // Option B: place exact tHalf[pos] char and continue matching
            if (avail[tChar] > 0) {
                avail[tChar]--;
                builtHalf[pos] = (char) ('a' + tChar);
                // Continue to next position
            } else {
                // Can't match prefix anymore, stop
                break;
            }

            // If we've matched entire tHalf
            if (pos == halfLen - 1) {
                // leftHalf == tHalf, palindrome > target only if:
                // n is odd AND mid > target[halfLen]
                if (n % 2 != 0 && mid > target.charAt(halfLen)) {
                    String candidate = buildPalindrome(builtHalf, mid, n);
                    if (bestCandidate == null || candidate.compareTo(bestCandidate) < 0)
                        bestCandidate = candidate;
                }
                // Also: leftHalf == tHalf but palindrome's right half is mirror
                // Palindrome = leftHalf + [mid] + reverse(leftHalf)
                // Compare full palindrome with target
                String candidate = buildPalindrome(builtHalf, mid, n);
                if (candidate.compareTo(target) > 0) {
                    if (bestCandidate == null || candidate.compareTo(bestCandidate) < 0)
                        bestCandidate = candidate;
                }
            }
        }

        return bestCandidate != null ? bestCandidate : "";
    }

    private char[] buildSmallestHalf(int[] freq, int halfLen) {
        char[] half = new char[halfLen];
        int idx = 0;
        for (int i = 0; i < 26; i++)
            for (int j = 0; j < freq[i] / 2; j++)
                half[idx++] = (char) ('a' + i);
        return half;
    }

    private String buildPalindrome(char[] half, char mid, int n) {
        StringBuilder sb = new StringBuilder();
        for (char c : half) sb.append(c);
        if (n % 2 != 0) sb.append(mid);
        for (int i = half.length - 1; i >= 0; i--) sb.append(half[i]);
        return sb.toString();
    }
}

class Solution:
    def lexPalindromicPermutation(self, s: str, target: str) -> str:
        n = len(s)
        freq = [0] * 26

        for c in s:
            freq[ord(c) - ord('a')] += 1

        # Palindrome possible only if at most 1 odd frequency
        odd_count = sum(f % 2 for f in freq)

        if odd_count > 1:
            return ""

        # Middle character for odd length
        mid = ''
        for i in range(26):
            if freq[i] % 2:
                mid = chr(ord('a') + i)
                break

        half_len = n // 2

        # Build smallest left half
        smallest_half = []
        for i in range(26):
            smallest_half.extend(
                [chr(ord('a') + i)] * (freq[i] // 2)
            )

        smallest = self.build_palindrome(
            smallest_half, mid, n
        )

        if smallest > target:
            return smallest

        # Target's left half
        t_half = target[:half_len]

        # Available characters for left half
        avail = [f // 2 for f in freq]

        built_half = [''] * half_len
        best_candidate = None

        for pos in range(half_len):
            t_char = ord(t_half[pos]) - ord('a')

            # Try a character greater than target[pos]
            for c in range(t_char + 1, 26):
                if avail[c] > 0:
                    avail[c] -= 1
                    built_half[pos] = chr(ord('a') + c)

                    temp_avail = avail[:]
                    temp_half = built_half[:]

                    idx = pos + 1

                    for cc in range(26):
                        for _ in range(temp_avail[cc]):
                            if idx < half_len:
                                temp_half[idx] = chr(
                                    ord('a') + cc
                                )
                                idx += 1

                    candidate = self.build_palindrome(
                        temp_half, mid, n
                    )

                    if (
                        best_candidate is None
                        or candidate < best_candidate
                    ):
                        best_candidate = candidate

                    avail[c] += 1
                    break

            # Try to match target exactly
            if avail[t_char] > 0:
                avail[t_char] -= 1
                built_half[pos] = chr(ord('a') + t_char)
            else:
                break

            # Entire left half matched
            if pos == half_len - 1:
                candidate = self.build_palindrome(
                    built_half, mid, n
                )

                if candidate > target:
                    if (
                        best_candidate is None
                        or candidate < best_candidate
                    ):
                        best_candidate = candidate

        return best_candidate if best_candidate else ""

    def build_palindrome(self, half, mid, n):
        result = ''.join(half)

        if n % 2:
            result += mid

        result += ''.join(reversed(half))

        return result

class Solution {
public:
    string lexPalindromicPermutation(string s, string target) {
        int n = s.size();

        vector<int> freq(26, 0);

        for (char c : s) {
            freq[c - 'a']++;
        }

        // Palindrome possible only if at most 1 odd frequency
        int oddCount = 0;

        for (int f : freq) {
            if (f % 2 != 0) {
                oddCount++;
            }
        }

        if (oddCount > 1) {
            return "";
        }

        // Middle character for odd length
        char mid = 0;

        for (int i = 0; i < 26; i++) {
            if (freq[i] % 2 != 0) {
                mid = 'a' + i;
                break;
            }
        }

        int halfLen = n / 2;

        // Build smallest left half
        vector<char> smallestHalf;

        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < freq[i] / 2; j++) {
                smallestHalf.push_back('a' + i);
            }
        }

        string smallest = buildPalindrome(
            smallestHalf, mid, n
        );

        if (smallest > target) {
            return smallest;
        }

        // Target's left half
        string tHalf = target.substr(0, halfLen);

        // Available characters
        vector<int> avail(26);

        for (int i = 0; i < 26; i++) {
            avail[i] = freq[i] / 2;
        }

        vector<char> builtHalf(halfLen);
        string bestCandidate = "";

        for (int pos = 0; pos < halfLen; pos++) {
            int tChar = tHalf[pos] - 'a';

            // Try a character greater than target[pos]
            for (int c = tChar + 1; c < 26; c++) {
                if (avail[c] > 0) {

                    avail[c]--;
                    builtHalf[pos] = 'a' + c;

                    vector<int> tempAvail = avail;
                    vector<char> tempHalf = builtHalf;

                    int idx = pos + 1;

                    for (int cc = 0; cc < 26; cc++) {
                        for (int j = 0; j < tempAvail[cc]; j++) {
                            if (idx < halfLen) {
                                tempHalf[idx++] = 'a' + cc;
                            }
                        }
                    }

                    string candidate = buildPalindrome(
                        tempHalf, mid, n
                    );

                    if (
                        bestCandidate.empty() ||
                        candidate < bestCandidate
                    ) {
                        bestCandidate = candidate;
                    }

                    avail[c]++;
                    break;
                }
            }

            // Try to match target exactly
            if (avail[tChar] > 0) {
                avail[tChar]--;
                builtHalf[pos] = 'a' + tChar;
            } else {
                break;
            }

            // Entire left half matched
            if (pos == halfLen - 1) {
                string candidate = buildPalindrome(
                    builtHalf, mid, n
                );

                if (candidate > target) {
                    if (
                        bestCandidate.empty() ||
                        candidate < bestCandidate
                    ) {
                        bestCandidate = candidate;
                    }
                }
            }
        }

        return bestCandidate;
    }

private:
    string buildPalindrome(
        vector<char>& half,
        char mid,
        int n
    ) {
        string result;

        for (char c : half) {
            result += c;
        }

        if (n % 2 != 0) {
            result += mid;
        }

        for (int i = half.size() - 1; i >= 0; i--) {
            result += half[i];
        }

        return result;
    }
};

class Solution {
    lexPalindromicPermutation(s, target) {
        const n = s.length;
        const freq = new Array(26).fill(0);

        for (const c of s) {
            freq[c.charCodeAt(0) - 97]++;
        }

        // Palindrome possible only if at most 1 odd frequency
        let oddCount = 0;

        for (const f of freq) {
            if (f % 2 !== 0) {
                oddCount++;
            }
        }

        if (oddCount > 1) {
            return "";
        }

        // Middle character for odd length
        let mid = "";

        for (let i = 0; i < 26; i++) {
            if (freq[i] % 2 !== 0) {
                mid = String.fromCharCode(97 + i);
                break;
            }
        }

        const halfLen = Math.floor(n / 2);

        // Build smallest left half
        const smallestHalf = [];

        for (let i = 0; i < 26; i++) {
            for (let j = 0; j < Math.floor(freq[i] / 2); j++) {
                smallestHalf.push(
                    String.fromCharCode(97 + i)
                );
            }
        }

        const smallest = this.buildPalindrome(
            smallestHalf,
            mid,
            n
        );

        if (smallest > target) {
            return smallest;
        }

        // Target's left half
        const tHalf = target.substring(0, halfLen);

        // Available characters
        const avail = new Array(26).fill(0);

        for (let i = 0; i < 26; i++) {
            avail[i] = Math.floor(freq[i] / 2);
        }

        const builtHalf = new Array(halfLen);
        let bestCandidate = "";

        for (let pos = 0; pos < halfLen; pos++) {
            const tChar = tHalf.charCodeAt(pos) - 97;

            // Try a character greater than target[pos]
            for (let c = tChar + 1; c < 26; c++) {
                if (avail[c] > 0) {

                    avail[c]--;
                    builtHalf[pos] =
                        String.fromCharCode(97 + c);

                    const tempAvail = [...avail];
                    const tempHalf = [...builtHalf];

                    let idx = pos + 1;

                    for (let cc = 0; cc < 26; cc++) {
                        for (let j = 0; j < tempAvail[cc]; j++) {
                            if (idx < halfLen) {
                                tempHalf[idx++] =
                                    String.fromCharCode(97 + cc);
                            }
                        }
                    }

                    const candidate =
                        this.buildPalindrome(
                            tempHalf,
                            mid,
                            n
                        );

                    if (
                        bestCandidate === "" ||
                        candidate < bestCandidate
                    ) {
                        bestCandidate = candidate;
                    }

                    avail[c]++;
                    break;
                }
            }

            // Try to match target exactly
            if (avail[tChar] > 0) {
                avail[tChar]--;
                builtHalf[pos] =
                    String.fromCharCode(97 + tChar);
            } else {
                break;
            }

            // Entire left half matched
            if (pos === halfLen - 1) {
                const candidate =
                    this.buildPalindrome(
                        builtHalf,
                        mid,
                        n
                    );

                if (candidate > target) {
                    if (
                        bestCandidate === "" ||
                        candidate < bestCandidate
                    ) {
                        bestCandidate = candidate;
                    }
                }
            }
        }

        return bestCandidate;
    }

    buildPalindrome(half, mid, n) {
        let result = half.join("");

        if (n % 2 !== 0) {
            result += mid;
        }

        result += [...half].reverse().join("");

        return result;
    }
}