Leetcode 1520. Maximum Number of Non-Overlapping Substrings

문제

소문자로 이루어진 문자열 s가 주어진다.

다음 조건을 만족하는 비어 있지 않은 부분 문자열(substring)들을 최대한 많이 찾아야 한다.

1. 선택한 부분 문자열들은 서로 겹치지 않아야 한다.
   즉, 두 부분 문자열이 s[i..j]와 s[x..y]라면, 반드시 j < x 또는 i > y여야 한다.

2. 어떤 부분 문자열이 특정 문자 c를 포함한다면, 그 부분 문자열은 문자열 s에 존재하는 모든 c의 위치를 포함해야 한다.

위 조건을 만족하는 부분 문자열들의 개수가 최대가 되도록 선택하라.

만약 최대 개수를 만족하는 방법이 여러 개라면, 선택한 부분 문자열들의 전체 길이 합이 가장 작은 방법을 반환하라.

전체 길이의 합이 최소인 해답은 유일하게 존재함을 증명할 수 있다.

선택한 부분 문자열들은 어떤 순서로 반환해도 된다.

---

예시

입력: s = "adefaddaccc"
출력: ["e","f","ccc"]

설명:

다음은 조건을 만족하는 가능한 모든 부분 문자열이다.

[
  "adefaddaccc",
  "adefadda",
  "ef",
  "e",
  "f",
  "ccc",
]

첫 번째 문자열 "adefaddaccc"를 선택하면 다른 부분 문자열은 아무것도 선택할 수 없으므로, 선택 가능한 부분 문자열의 개수는 1개가 된다.

"adefadda"를 선택하면 겹치지 않는 부분 문자열로 "ccc"만 추가로 선택할 수 있으므로, 총 2개의 부분 문자열을 선택할 수 있다.

또한 "ef"를 선택하는 것은 최적이 아니다. "ef"는 "e"와 "f"라는 두 개의 부분 문자열로 나눠서 각각 선택할 수 있기 때문이다.

따라서 최적의 선택은 ["e","f","ccc"]이며, 총 3개의 부분 문자열을 얻을 수 있다.

같은 개수인 3개의 부분 문자열을 선택하는 다른 해답은 존재하지 않는다.

---

제한

• $1 <= s.length <= 10^5$
• s는 영어 소문자로만 이루어져 있다.

---

풀이

1. 각 알파벳에 대해 첫 등장 위치와 마지막 등장 위치를 기록한다.

2. 각 알파벳의 첫 등장 위치와 마지막 등장 위치 사이에 있는 알파벳들을 검사한다.

   • 이때 범위 안의 어떤 알파벳이 현재 시작점보다 앞에서 등장한 적이 있다면, 해당 범위는 조건을 만족할 수 없으므로 사용하지 않는다.
   • 반대로 해당 알파벳의 마지막 등장 위치가 현재 끝점보다 뒤에 있다면, 끝점을 그 위치까지 확장하고 계속 검사한다.

3. 이렇게 유효한 인터벌을 모두 만든 뒤, 끝나는 위치가 빠른 순서대로 정렬하여 서로 겹치지 않는 인터벌을 선택한다.

from collections import defaultdict

class Solution:
    def maxNumOfSubstrings(self, s: str) -> list[str]:
        bounds = defaultdict(lambda: [-1, -1])

        for i, ch in enumerate(s):
            if bounds[ch][0] == -1:
                bounds[ch][0] = i
            bounds[ch][1] = i

        intervals = []

        for start, end in bounds.values():
            i = start + 1

            while i < end:
                target_start, target_end = bounds[s[i]]

                if target_start < start:
                    break

                end = max(end, target_end)
                i += 1
            else:
                intervals.append((start, end))

        intervals.sort(key=lambda x: (x[1], -x[0]))

        ans = []
        prev_end = -1

        for start, end in intervals:
            if start > prev_end:
                ans.append(s[start:end + 1])
                prev_end = end

        return ans