3720. Lexicographically Smallest Permutation Greater Than Target

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

Return the lexicographically smallest permutation of s that is strictly greater than target. If no permutation of s is lexicographically strictly greater than target, return an empty string.

A string a is lexicographically strictly greater than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b.

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

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

            freq[i] += 1;
            if(i != start) return false;
        }
        return false;
    }
public:
    string lexGreaterPermutation(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 "";
    }
};