## 763. Partition Labels

A string `S` of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

```Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
```

Note:

1. `S` will have length in range `[1, 500]`.
2. `S` will consist of lowercase letters (`'a'` to `'z'`) only.

b'
\n
\n\n
\n

#### Approach #1: Greedy [Accepted]

\n

Intuition

\n

Let\'s try to repeatedly choose the smallest left-justified partition.\nConsider the first label, say it\'s `\'a\'`. The first partition must include it, and also the last occurrence of `\'a\'`.\nHowever, between those two occurrences of `\'a\'`, there could be other labels that make the minimum size of this partition bigger. For example, in `"abccaddbeffe"`, the minimum first partition is `"abccaddb"`. \nThis gives us the idea for the algorithm: For each letter encountered, process the last occurrence of that letter, extending the current partition `[anchor, j]` appropriately.

\n

Algorithm

\n

We need an array `last[char] -> index of S where char occurs last`.\nThen, let `anchor` and `j` be the start and end of the current partition.\nIf we are at a label that occurs last at some index after `j`, we\'ll extend the partition `j = last[c]`. If we are at the end of the partition (`i == j`) then we\'ll append a partition size to our answer, and set the start of our new partition to `i+1`.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of .

\n
• \n
• \n

Space Complexity: .

\n
• \n
\n
\n

Analysis written by: @awice.

\n
'