[LeetCode] 763 | Partition Labels | Python

---

문제 링크: https://leetcode.com/problems/partition-labels/

---

문제

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

---

조건

• 1 <= s.length <= 500
• s consists of lowercase English letters.

---

내 풀이

알파벳이 나오는 index를 count에 저장한다.

s를 앞에서부터 차례로 훑으면서 maxi에 현재의 알파벳이 뒤에 또 나오면, 그 index를 저장한다.

---

---

---

---

---

---

---

코드

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        sList = list(s)
        count = [[] for _ in range(26)]
        ans = []
        
        for idx, char in enumerate(sList):
            count[ord(char) - ord('a')].append(idx)

        maxi = 0
        for idx, char in enumerate(sList):
            alphabet = ord(char) - ord('a')
            
            del count[alphabet][0]
            if len(count[alphabet]):
                maxi = max(maxi, count[alphabet][0])

            if maxi == idx:
                if len(ans) == 0:
                    ans.append(maxi+1)
                else:
                    ans.append(maxi-sum(ans)+1)
                maxi = idx+1
        
        if maxi-sum(ans)+1 > 0:
            ans.append(maxi-sum(ans)+1)
                
        return ans[:-1]