763. Partition Labels

[zeikar]

Problem link

https://leetcode.com/problems/partition-labels/

Problem Summary

문자열을 각 문자들이 최대 한 덩어리에만 있도록 나눠야 한다. 최대한 많이 나눌 때의 덩어리 개수를 구하는 문제.

Solution

잘 생각해보면 한 덩어리에만 있어야 한다는 것은 다음 덩어리에는 해당 문자가 나타나서는 안 된다는 것이다. 다음 문자가 어디 있는지 map을 통해 위치를 저장해두고 현재 덩어리의 모든 문자가 뒤에 나타나지 않으면 한 덩어리로 묶을 수 있다.
위치는 하나만 있으면 되므로 문자의 마지막 위치를 저장해주면 된다.

Source Code

from typing import List


class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        pos = {}

        for i in range(len(s)):
            pos[s[i]] = i

        ans = []
        chunk = []

        for i in range(len(s)):
            chunk.append(s[i])

            split = True

            for j in range(len(chunk)):
                if pos[chunk[j]] > i:
                    split = False
                    break

            if split:
                ans.append(len(chunk))
                chunk = []

        return ans