3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

You are given two strings s and target, each of length n, consisting of lowercase English letters.

Return the lexicographically smallest string that is both a palindromic permutation of s and strictly greater than target. If no such permutation exists, return an empty string.

class Solution {
    bool helper(string& s, vector<int>& freq, string& now, int l, int r, bool over) {
        if(l > r) return now > s;
        if(l == r) {
            int who = max_element(begin(freq), end(freq)) - begin(freq);
            now[l] = who + 'a';
            freq[who]--;
            if(helper(s,freq,now,l+1,r-1,over)) return true;
            freq[who]++;
            return false;
        }
        if(over) {
            for(int i = 0; i < 26; i++) {
                if(freq[i] < 2) continue;
                freq[i] -= 2;
                now[l] = now[r] = i + 'a';
                if(helper(s,freq,now,l+1,r-1,true)) return true;
                freq[i] += 2;
                return false;
            }
            return false;
        }
        for(int start = s[l] - 'a', i = start; i < 26; i++) {
            if(freq[i] < 2) continue;

            freq[i] -= 2;
            now[l] = now[r] = i + 'a';

            if(helper(s,freq,now,l+1,r-1,start != i)) return true;

            freq[i] += 2;
            if(i != start) return false;
        }
        return false;
    }
public:
    string lexPalindromicPermutation(string s, string target) {
        vector<int> freq(26);
        for(auto& ch : s) freq[ch-'a']++;
        string now = string(s.length(), '#');
        if(helper(target, freq, now, 0, target.size() - 1, false)) return now;
        return "";
    }
};