Leetcode 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.

길이가 n인 두 문자열 s와 target이 주어집니다. 두 문자열은 모두 영문 소문자로만 이루어져 있습니다.

s의 모든 순열 중에서 target보다 사전순으로 엄격하게 큰 문자열 가운데 가장 작은 문자열을 반환하세요.

만약 target보다 사전순으로 엄격하게 큰 s의 순열이 존재하지 않는다면 빈 문자열 ""을 반환하세요.

같은 길이의 두 문자열 a, b에 대해, 두 문자열이 처음으로 달라지는 위치에서 a의 문자가 b의 문자보다 알파벳 순서상 뒤에 있다면 a는 b보다 사전순으로 엄격하게 크다고 합니다.

---

예시

입력: s = "leet", target = "code"

출력: "eelt"

설명:

• s의 모든 순열을 사전순으로 나열하면 "eelt", "eetl", "elet", "elte", "etel", "etle", "leet", "lete", "ltee", "teel", "tele", "tlee"입니다.
• 이 중 target보다 사전순으로 엄격하게 큰 순열 가운데 가장 작은 것은 "eelt"입니다.

---

제한

• $1 \le s.length == target.length \le 300$
• s와 target은 영어 소문자로만 이루어져 있다.

---

풀이

먼저 s에 포함된 각 문자의 개수를 카운팅한다.

우리가 원하는 것은 target보다 사전순으로 크면서도 그중 가장 작은 문자열이다.
따라서 가능한 동안에는 결과 문자열의 앞부분을 target과 최대한 동일하게 맞추는 것이 유리하다.

target의 앞쪽 문자부터 확인하면서 해당 문자가 아직 남아 있다면 그대로 사용한다.
더 이상 target[index]와 같은 문자를 사용할 수 없는 위치가 나오면, 지금까지 만든 접두사를 기준으로 target보다 커질 수 있는 가장 작은 문자를 찾는다.

현재 위치에서 target[index]보다 큰 문자 중 가장 작은 문자를 사용할 수 있다면, 그 문자를 선택하는 순간 결과 문자열은 이미 target보다 커진다.
이후 남은 자리에는 남아 있는 문자들을 오름차순으로 채우면, 가능한 문자열 중 사전순으로 가장 작은 결과가 된다.

문제는 현재 위치에서 더 큰 문자를 선택할 수 없는 경우다.

이때는 지금까지 만든 문자열의 뒤쪽부터 한 글자씩 되돌린다.
되돌린 문자를 다시 사용 가능한 문자 개수에 추가한 뒤, 그 위치에서 target의 문자보다 큰 문자를 선택할 수 있는지 다시 확인한다.

즉,

1. 가능한 한 target과 동일한 접두사를 만든다.
2. 현재 위치에서 target보다 큰 가장 작은 문자를 찾는다.
3. 찾았다면 남은 문자들을 오름차순으로 붙여 반환한다.
4. 찾지 못했다면 한 칸 뒤로 돌아가 같은 과정을 반복한다.

끝까지 되돌렸는데도 target보다 큰 문자열을 만들 수 없다면 ""을 반환한다.

class Solution:
    def lexGreaterPermutation(self, s: str, target: str) -> str:
        N = len(s)

        def i(character: str) -> int:
            return ord(character) - ord('a')

        def c(number: int) -> str:
            return chr(number + ord('a'))

        original = [0] * 26
        for ch in s:
            original[i(ch)] += 1

        index = 0
        ans = []

        while index < N:
            if original[i(target[index])] == 0:
                break

            ans.append(target[index])
            original[i(target[index])] -= 1
            index += 1

        while index >= 0:
            if index < N:
                tgt = i(target[index])

                for check in range(tgt + 1, 26):
                    if original[check] > 0:
                        ans.append(c(check))
                        original[check] -= 1

                        for adder in range(26):
                            ans.extend([c(adder)] * original[adder])

                        return "".join(ans)

            index -= 1
            if ans:
                removed = ans.pop()
                original[i(removed)] += 1

        return ""