1520. Maximum Number of Non-Overlapping Substrings

[zeikar]

Problem Link

https://leetcode.com/problems/maximum-number-of-non-overlapping-substrings/

Problem Summary

어떤 문자를 담으면 그 문자가 나오는 모든 위치를 담아야 한다는 조건 아래, 겹치지 않는 부분 문자열을 최대 개수로 고르는 문제.

Solution

일단 알파벳별로 first, last 인덱스를 뽑아둔다. 시작점 후보는 각 알파벳의 first, 26개뿐이다.

거기서 오른쪽으로 훑으면서 보이는 문자의 last로 end를 늘려주면 된다. 대신 중간에 first[cc] < start인 문자를 만나면 그 시도는 폐기한다. 왼쪽으로 넓혀야 하는 경우인데, 어차피 그 문자의 first에서 시작하는 시도가 같은 구간을 만드니까 그냥 버려도 된다.

이렇게 나온 후보는 서로 포함이거나 완전히 분리고, 걸치는 경우가 없다. [a1, b1]이 유효하면 그 안의 문자는 전부 last <= b1이라 안쪽에서 시작한 구간이 b1을 못 넘기 때문. 그래서 끝점 기준으로 정렬해서 겹치지 않으면 집는 그리디로 개수만 최대로 맞춰주면, 겹치는 후보는 항상 포함 관계라 안쪽=짧은 쪽을 집게 되고 길이 합 최소도 저절로 따라온다.

시간복잡도는 O(26n).

아이디어는 여기까지 나왔는데 구현이 좀 복잡해서 결국 claude의 도움을 받았다.

그리고 다시 보니 정답 구간은 항상 꽉 차 있다. 중간에 다른 문자가 끼어들 수가 없다. 이걸 그대로 판정으로 쓰는 풀이가 있는데, 문자 집합의 first 최소를 left, last 최대를 right, 등장 횟수 합을 total이라고 하면 total == right - left + 1인 순간이 곧 유효한 구간이다. 꽉 찼다는 게 딱 이 식이다. 문자를 first 순서로 큐에 넣으면서 최근 것부터 누적하다가 식이 성립하면 그 구간을 집고 큐를 비워주면 된다. 문자열을 다시 훑을 일이 없어서 26개짜리 레코드만 만지면 되고, n = 100000에서 6~10배 빨랐다. 아래 디스커션 참고함.

https://leetcode.com/problems/maximum-number-of-non-overlapping-substrings/solutions/8527189/100-hard-problem-with-easy-approach-with-il3v/

Source Code

class Solution:
    def maxNumOfSubstrings(self, s: str) -> List[str]:
        first, last = {}, {}
        for i, c in enumerate(s):
            if c not in first:
                first[c] = i
            last[c] = i

        intervals = []
        for c in first:
            start, end = first[c], last[c]
            ok = True
            i = start
            while i <= end:
                cc = s[i]
                if first[cc] < start:
                    ok = False
                    break
                end = max(end, last[cc])
                i += 1
            if ok:
                intervals.append((end, start))

        intervals.sort()

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