763.md

Partition Labels

Description

link

---

Solution

• Record last appear position for each characters
• Using slide window to match part where all same characters are included
  • update j with max(j, last_char(S[i]))
  • update span and i with 1 step each time
• Dont forget to update i after append result

---

Code

O(n)

class Solution:
    def partitionLabels(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        last_char = {}
        for i in range(len(S) - 1, -1, -1):
            if S[i] not in last_char:
                last_char[S[i]] = i
        
        result = []
        i = 0
        while i < len(S):
            span = 1
            j = last_char[S[i]]
            while i != j:
                i += 1
                j = max(j, last_char[S[i]])
                span += 1
            result.append(span)
            i += 1
        
        return result