[리트코드] 3720 - Lexicographically Smallest Permutation Greater Than Target

3720. Lexicographically Smallest Permutation Greater Than Target

Medium

---

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.

 

Example 1:

Example 2:

Example 3:

 

Constraints:

• 1 <= s.length == target.length <= 300
• s and target consist of only lowercase English letters.

분류

해시 테이블, 문자열, 그리디, 카운팅, 완전 탐색

---

문제 풀이

문제 분석

이 문제는 두 개의 문자열 s와 target이 주어질 때, s의 문자들로 만들 수 있는 순열 중에서 target보다 사전식(lexicographically)으로 엄격하게 큰 가장 작은 순열을 찾아 반환하는 문제입니다. 만약 그러한 순열이 존재하지 않으면 빈 문자열을 반환해야 합니다. 입력 문자열 s와 target의 길이는 같으며, 소문자 영어 알파벳으로만 구성됩니다. 길이는 1부터 300까지 가능합니다.

사전식으로 더 크다는 것은, 두 문자열이 처음으로 달라지는 위치에서 한 문자열의 문자가 다른 문자열의 해당 문자보다 알파벳 순서상 뒤에 오는 경우를 의미합니다. 예를 들어, "abc"는 "abb"보다 사전식으로 큽니다.

접근 방법

이 문제는 모든 s의 순열을 생성하여 확인하는 방식으로 접근하면 시간 복잡도가 N!이 되어 N=300일 때 해결 불가능합니다. 따라서 그리디(greedy) 방식을 사용하여 효율적으로 가장 작은 순열을 찾아야 합니다.

핵심 아이디어는 다음과 같습니다:

1. 최대한 target과 유사하게 만들기: 사전식으로 가장 작은 순열을 찾기 위해서는 target의 최대한 많은 부분을 그대로 유지하는 것이 좋습니다. 즉, target의 앞부분과 일치하는 부분이 길수록 결과가 사전식으로 작아질 가능성이 높습니다.
2. 최초의 "더 커지는" 위치 찾기: target의 앞부분을 result의 앞부분으로 그대로 사용하다가, 어떤 인덱스 i에서 result[i]가 target[i]보다 커지도록 만들어야 합니다. 이때 result[i]는 target[i]보다 크면서도 가장 작은 가능한 문자를 선택해야 합니다.
3. 나머지 부분 정렬: result[i]를 선택한 후, result의 나머지 뒷부분(result[i+1]부터 result[n-1])은 남은 문자들을 사용하여 사전식으로 가장 작은 형태로 채워야 합니다. 이는 남은 문자들을 알파벳 순서로 정렬하여 배치하는 것을 의미합니다.

이러한 조건을 만족시키기 위해, 우리는 target의 오른쪽 끝에서부터 왼쪽으로(n-1부터 0까지) 탐색합니다. 그 이유는 오른쪽에서부터 변경하는 것이 전체 순열을 사전식으로 덜 변경하기 때문에, 더 작은 결과값을 찾을 가능성이 높아지기 때문입니다.

문자 사용 가능 여부를 효율적으로 확인하기 위해 Counter를 사용하여 s에 있는 각 문자의 개수를 추적합니다.

구현 설명

1. 문자 빈도수 초기화 및 슬라이딩 윈도우 준비

• s의 문자별 빈도수를 cnt 딕셔너리(Counter 객체)에 저장합니다.
• 이후 target의 모든 문자를 cnt에서 한 번씩 감소시킵니다.
  • 초기 cnt는 s에 있는 모든 문자의 빈도수를 가집니다.
  • target의 문자를 모두 빼는 것은, 코드의 메인 반복문에서 cnt[target[i]] += 1과 결합되어, 인덱스 i에서 target[0...i-1]까지의 문자를 사용했을 때 남은 문자들의 빈도수를 효율적으로 계산하는 기반을 마련합니다.
  • 즉, cnt는 Counter(s) - Counter(target) 상태가 됩니다.

2. 가능한 가장 오른쪽 인덱스 찾기

• n-1부터 0까지 i를 감소시키면서 반복합니다. 여기서 i는 결과 순열이 target과 달라지기 시작할 가능성이 있는 위치를 나타냅니다.
• 매 반복마다 cnt[target[i]] += 1을 수행합니다.
  • 이 동작으로 cnt는 Counter(s) - Counter(target[0...i-1]) 상태가 됩니다. 즉, target의 i번째 문자부터 끝까지의 문자들은 이제 "사용할 수 있는" 문자 풀에 다시 추가된 것으로 간주합니다. 이 cnt는 target의 0부터 i-1까지의 접두사를 사용했을 때 s에서 남는 문자들의 개수를 정확히 반영합니다.
• any(x < 0 for x in cnt.values())를 통해 현재 cnt에 음수 값이 있는지 확인합니다.
  • 만약 음수 값이 있다면, target[0...i-1] 접두사를 s의 문자로 구성하는 것 자체가 불가능하다는 의미입니다. 이 경우에는 현재 i 위치에서 target[i]를 변경하려고 시도할 수 없으므로 다음 i로 넘어갑니다 (continue).

3. 대체 문자 찾기 및 순열 생성

• cnt에 음수 값이 없어 현재 target[0...i-1] 접두사를 구성할 수 있다면, 이제 i번째 위치에 들어갈 문자를 찾습니다.
• target[i]보다 크면서 cnt에 남아있는(cnt[ch] > 0) 가장 작은 문자 ch를 찾습니다. 이를 위해 ord(target[i]) + 1부터 ord('z') + 1까지 반복합니다.
• 적합한 ch를 찾았다면:
  • cnt[ch] -= 1를 통해 ch를 사용한 것으로 표시합니다.
  • 남은 문자들로 rest 문자열을 생성합니다. cnt에 남아있는 모든 문자를 알파벳 순서로 정렬하여 붙여 만듭니다. (예: {'a':2, 'c':1} 이면 "aac"). "".join(chr(k) * cnt[chr(k)] for k in range(ord('a'), ord('z') + 1) if cnt[chr(k)] > 0) 이 부분이 이를 수행합니다.
  • 최종 결과는 target[:i] (기존 target의 접두사) + ch (새로운 문자) + rest (나머지 정렬된 문자들)가 됩니다. 이 문자열을 반환합니다.

4. 결과 없음 처리

• 만약 n-1부터 0까지 모든 i를 탐색했음에도 적절한 순열을 찾지 못했다면, s의 어떤 순열도 target보다 사전식으로 클 수 없다는 의미입니다. 이 경우 빈 문자열 ""을 반환합니다.

⏱복잡도 분석

• 시간 복잡도:

  • cnt = Counter(s): O(N) (N은 문자열의 길이)
  • for i in target: cnt[i] -= 1: O(N)
  • 메인 for i in range(n - 1, -1, -1) 루프: N번 반복합니다.
    • cnt[target[i]] += 1: O(1)
    • any(x < 0 for x in cnt.values()): 딕셔너리의 모든 26개 키를 확인합니다. O(1) (알파벳 크기는 상수)
    • 내부 for c in range(...) 루프: 최대 26번 반복합니다. O(1)
      • cnt[ch] -= 1: O(1)
      • "".join(...)으로 rest 문자열 생성: N - (i+1)개의 문자를 합치며, 최대 26개의 chr(k) * cnt[chr(k)] 연산을 포함합니다. 이 작업은 문자열의 길이에 비례하므로 O(N)이 됩니다.
  • 따라서 전체 시간 복잡도는 O(N * (1 + 1 + 1 + N)) = O(N^2)가 됩니다. N이 최대 300이므로 N^2 = 90,000으로 충분히 효율적입니다.

• 공간 복잡도:

  • cnt = Counter(s): 알파벳 26개 문자의 빈도수를 저장하므로 O(1) (알파벳 크기는 상수)
  • target[:i]: 부분 문자열을 생성할 때 최대 O(N)의 공간이 필요할 수 있습니다.
  • rest 문자열: 최대 O(N)의 공간이 필요할 수 있습니다.
  • 결과 문자열: O(N)
  • 따라서 전체 공간 복잡도는 O(N)입니다.

핵심 포인트

1. 그리디 (Greedy) 전략과 역방향 탐색: 사전식으로 가장 작은 순열을 찾기 위해, target의 접두사를 최대한 유지하고, 가장 오른쪽(n-1)에서부터 변경을 시도합니다. 이는 변경이 전체 순열에 미치는 영향을 최소화하여 사전식으로 더 작은 결과를 얻을 가능성을 높입니다.
2. 효율적인 문자 빈도수 관리: Counter를 사용하여 s의 문자 빈도수를 Counter(s) - Counter(target) 형태로 초기화한 후, 메인 루프에서 cnt[target[i]] += 1 연산을 통해 각 i 단계에서 target[0...i-1] 접두사를 사용했을 때 남은 문자들의 빈도수를 O(1) 시간 복잡도로 유지합니다. 이는 target[0...i-1] 접두사를 s의 문자로 만들 수 있는지 여부를 효율적으로 판단하게 해줍니다.
3. 사전식으로 가장 작은 접미사 구성: target[0...i-1] 접두사와 i번째에 올 문자 ch를 결정한 후에는, 남은 문자들을 사전식으로 오름차순 정렬하여 뒤에 붙여야 전체 결과가 최소가 됩니다. "".join(chr(k) * cnt[chr(k)] for k in range(ord('a'), ord('z') + 1) if cnt[chr(k)] > 0) 구문이 이 부분을 담당합니다.

풀이 코드

from collections import Counter

class Solution:
    def lexGreaterPermutation(self, s: str, target: str) -> str:
        n = len(s)
        cnt = Counter(s)
        
        for i in target:
            cnt[i] -= 1
            
        for i in range(n - 1, -1, -1):
            cnt[target[i]] += 1
            
            if any(x < 0 for x in cnt.values()):
                continue
            
            for c in range(ord(target[i]) + 1, ord('z') + 1):
                ch = chr(c)
                if cnt[ch] > 0:
                    cnt[ch] -= 1
                    rest = "".join(chr(k) * cnt[chr(k)] for k in range(ord('a'), ord('z') + 1) if cnt[chr(k)] > 0)
                    
                    return target[:i] + ch + rest
                    
        return ""