This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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:**

`S`

will have length in range`[1, 500]`

.`S`

will consist of lowercase letters (`'a'`

to`'z'`

) only.

b'

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

\n

\n

'
\n\n

\n**Intuition**

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.

**Algorithm**

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`

.

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of .

\n \n - \n
Space Complexity: .

\n \n

\n

Analysis written by: @awice.

\n