3720. Lexicographically Smallest Permutation Greater Than Target

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

        int breakIndex = -1;
        int[] breakCnt = null;

        for (int i = 0; i < n; i++) {
            int tc = target.charAt(i) - 'a';

            // check if a character greater than target[i] is available right now
            boolean found = false;
            for (int c = tc + 1; c < 26; c++) {
                if (cnt[c] > 0) {
                    found = true;
                    break;
                }
            }
            if (found) {
                breakIndex = i;          // candidate breakpoint (keep the rightmost one)
                breakCnt = cnt.clone();  // save state at this point
            }

            // try to continue matching target as prefix
            if (cnt[tc] > 0) {
                cnt[tc]--;
            } else {
                break; // can't match prefix any further, no later breakpoints possible
            }
        }

        if (breakIndex == -1) {
            return ""; // no valid permutation strictly greater than target
        }

        StringBuilder sb = new StringBuilder();
        sb.append(target, 0, breakIndex); // matched prefix

        int tc = target.charAt(breakIndex) - 'a';
        int chosen = -1;
        for (int c = tc + 1; c < 26; c++) {
            if (breakCnt[c] > 0) {
                chosen = c;
                break;
            }
        }
        breakCnt[chosen]--;
        sb.append((char) ('a' + chosen)); // smallest char strictly greater than target[breakIndex]

        // fill the rest with remaining letters in ascending order (smallest arrangement)
        for (int c = 0; c < 26; c++) {
            for (int k = 0; k < breakCnt[c]; k++) {
                sb.append((char) ('a' + c));
            }
        }

        return sb.toString();
    }
}

class Solution:
    def lexGreaterPermutation(self, s, target):
        n = len(s)

        cnt = [0] * 26

        for ch in s:
            cnt[ord(ch) - ord('a')] += 1

        break_index = -1
        break_cnt = None

        for i in range(n):
            tc = ord(target[i]) - ord('a')

            # Check if a character greater than target[i] is available
            for c in range(tc + 1, 26):
                if cnt[c] > 0:
                    break_index = i
                    break_cnt = cnt[:]
                    break

            # Continue matching target as prefix
            if cnt[tc] > 0:
                cnt[tc] -= 1
            else:
                break

        if break_index == -1:
            return ""

        result = list(target[:break_index])

        tc = ord(target[break_index]) - ord('a')

        # Choose the smallest character greater than target[i]
        chosen = -1

        for c in range(tc + 1, 26):
            if break_cnt[c] > 0:
                chosen = c
                break

        break_cnt[chosen] -= 1
        result.append(chr(ord('a') + chosen))

        # Add remaining characters in ascending order
        for c in range(26):
            result.extend([chr(ord('a') + c)] * break_cnt[c])

        return ''.join(result)

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

        vector<int> cnt(26, 0);

        for (char ch : s) {
            cnt[ch - 'a']++;
        }

        int breakIndex = -1;
        vector<int> breakCnt;

        for (int i = 0; i < n; i++) {
            int tc = target[i] - 'a';

            // Check if a character greater than target[i] is available
            for (int c = tc + 1; c < 26; c++) {
                if (cnt[c] > 0) {
                    breakIndex = i;
                    breakCnt = cnt;
                    break;
                }
            }

            // Continue matching target as prefix
            if (cnt[tc] > 0) {
                cnt[tc]--;
            } else {
                break;
            }
        }

        if (breakIndex == -1) {
            return "";
        }

        string result = target.substr(0, breakIndex);

        int tc = target[breakIndex] - 'a';

        // Choose the smallest character greater than target[i]
        int chosen = -1;

        for (int c = tc + 1; c < 26; c++) {
            if (breakCnt[c] > 0) {
                chosen = c;
                break;
            }
        }

        breakCnt[chosen]--;
        result += char('a' + chosen);

        // Add remaining characters in ascending order
        for (int c = 0; c < 26; c++) {
            while (breakCnt[c]--) {
                result += char('a' + c);
            }
        }

        return result;
    }
};

class Solution {
    lexGreaterPermutation(s, target) {
        const n = s.length;

        const cnt = new Array(26).fill(0);

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

        let breakIndex = -1;
        let breakCnt = null;

        for (let i = 0; i < n; i++) {
            const tc = target.charCodeAt(i) - 97;

            // Check if a character greater than target[i] is available
            for (let c = tc + 1; c < 26; c++) {
                if (cnt[c] > 0) {
                    breakIndex = i;
                    breakCnt = [...cnt];
                    break;
                }
            }

            // Continue matching target as prefix
            if (cnt[tc] > 0) {
                cnt[tc]--;
            } else {
                break;
            }
        }

        if (breakIndex === -1) {
            return "";
        }

        const result = target.substring(0, breakIndex);

        const tc = target.charCodeAt(breakIndex) - 97;

        // Choose the smallest character greater than target[i]
        let chosen = -1;

        for (let c = tc + 1; c < 26; c++) {
            if (breakCnt[c] > 0) {
                chosen = c;
                break;
            }
        }

        breakCnt[chosen]--;

        let answer = result + String.fromCharCode(97 + chosen);

        // Add remaining characters in ascending order
        for (let c = 0; c < 26; c++) {
            while (breakCnt[c] > 0) {
                answer += String.fromCharCode(97 + c);
                breakCnt[c]--;
            }
        }

        return answer;
    }
}