# Partition Labels
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/partition-labels)
Canonical: https://scaleengineer.com/dsa/problems/partition-labels
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Hash Table, String
**Companies:** [Sprinklr](https://scaleengineer.com/companies/sprinklr), [InMobi](https://scaleengineer.com/companies/inmobi)
---
## Problem
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. For example, the string `"ababcc"` can be partitioned into `["abab", "cc"]`, but partitions such as `["aba", "bcc"]` or `["ab", "ab", "cc"]` are invalid.

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_.

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

**Example 2:**

**Input:** s = "eccbbbbdec"
**Output:** [10]

**Constraints:**

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

# Approaches
## Naive Iterative Search
This approach iteratively builds partitions without any pre-computation. For each potential partition, it determines its required boundary by finding the furthest last occurrence of any character within it. This process is repeated until the entire string is partitioned. The main drawback is the repeated work in finding last occurrences.
**Time:** O(N^2), where N is the length of the string. The `lastIndexOf` method takes O(N) time, and it is called within a loop that iterates through the string, leading to a quadratic time complexity. · **Space:** O(1), excluding the space required for the output list. Only a few variables are needed to keep track of indices.
**Pros:** Conceptually straightforward, directly implementing the definition of a valid partition.; Does not require extra space for pre-computation (besides the result list).
**Cons:** Inefficient due to repeated scanning of the string to find the last index of characters.; The time complexity is quadratic, which is slow for larger strings (though acceptable for the given constraints).
### Explanation
This method finds partitions one by one. It starts by considering the character at the current `start` index. It finds its last occurrence to define an initial partition boundary. Then, it iterates through all characters within this tentative partition, checking their last occurrences and extending the boundary if any character appears later in the string. This process continues until the partition boundary stabilizes, at which point a valid partition has been found.

The main inefficiency comes from repeatedly calling `s.lastIndexOf()` (or an equivalent manual search) for characters within the current potential partition. Since `lastIndexOf` scans a large part of the string and is called inside a loop that also iterates through the string, the overall complexity becomes quadratic.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> partitions = new ArrayList<>();
        int n = s.length();
        int start = 0;
        while (start < n) {
            // Find the furthest reach for the character at the start of the potential partition.
            int maxReach = s.lastIndexOf(s.charAt(start));
            
            // Iterate through the characters within the current partition range [start, maxReach]
            // and expand maxReach if any character extends further.
            for (int i = start + 1; i <= maxReach; i++) {
                maxReach = Math.max(maxReach, s.lastIndexOf(s.charAt(i)));
            }
            
            // Once the loop finishes, maxReach is the end of the current valid partition.
            int partitionSize = maxReach - start + 1;
            partitions.add(partitionSize);
            
            // Move to the start of the next partition.
            start = maxReach + 1;
        }
        return partitions;
    }
}
```
### Algorithm
- Initialize an empty list `partitions` and a `start` index to 0.
- Loop while `start` is less than the string length `n`:
  - Find the last occurrence of the character `s.charAt(start)`, let this be `maxReach`.
  - Iterate with an index `i` from `start` up to the current `maxReach`.
  - In the loop, update `maxReach` with the last occurrence of `s.charAt(i)` if it's greater than the current `maxReach`. This is done by calling a function like `s.lastIndexOf()`.
  - After the loop, `maxReach` marks the end of the minimal valid partition.
  - Add the size of this partition (`maxReach - start + 1`) to the `partitions` list.
  - Update `start` to `maxReach + 1`.
- Return the `partitions` list.

## Greedy Approach with Last Occurrences
This is an efficient greedy approach that solves the problem in linear time. It involves two passes over the string. The first pass records the last occurrence index of each character. The second pass then iterates through the string, using the pre-computed last indices to greedily find the smallest possible valid partition at each step.
**Time:** O(N), where N is the length of the string. The first pass to compute last indices takes O(N). The second pass to find partitions also takes O(N). The total time is O(N) + O(N) = O(N). · **Space:** O(1). We use an array of size 26 to store the last indices, which is constant space. The space for the result list is not counted in the complexity analysis.
**Pros:** Highly efficient with a linear time complexity.; The logic is elegant and easy to implement once the greedy strategy is understood.
**Cons:** Requires two passes over the input string.; Uses a small amount of extra space (O(1)) for the `lastIndices` array.
### Explanation
The core idea is that for a substring to be a valid partition, the last occurrence of every character within that substring must also be contained within that substring. To maximize the number of partitions, we should make each partition as small as possible.

This approach first pre-computes the last seen index for all 26 lowercase letters in a single pass. Then, in a second pass, it iterates through the string maintaining a `start` pointer for the current partition and an `end` pointer for the farthest reach of any character seen in the current partition. This `end` is updated greedily. When the iteration index `i` catches up to `end`, it signifies that we have found the smallest possible valid partition. We record its size and start looking for the next one.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> partitionLabels(String s) {
        if (s == null || s.length() == 0) {
            return new ArrayList<>();
        }
        
        // 1. Preprocessing: Find the last occurrence of each character.
        // An array is used as a hash map since characters are lowercase English letters.
        int[] lastIndices = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastIndices[s.charAt(i) - 'a'] = i;
        }
        
        List<Integer> result = new ArrayList<>();
        int start = 0;
        int end = 0;
        
        // 2. Partitioning: Iterate through the string to find partition boundaries.
        for (int i = 0; i < s.length(); i++) {
            // Greedily extend the end of the current partition to the farthest last occurrence.
            end = Math.max(end, lastIndices[s.charAt(i) - 'a']);
            
            // If the current index reaches the end of the partition,
            // it means we've found a complete, minimal partition.
            if (i == end) {
                result.add(end - start + 1);
                // Start a new partition from the next character.
                start = i + 1;
            }
        }
        
        return result;
    }
}
```
### Algorithm
- **First Pass (Preprocessing):**
  - Create an integer array `lastIndices` of size 26, initialized to 0.
  - Iterate through the input string `s` from `i = 0` to `n-1`.
  - For each character `s.charAt(i)`, store its index `i` in `lastIndices[s.charAt(i) - 'a']`.
- **Second Pass (Partitioning):**
  - Initialize an empty list `result`, `start = 0`, and `end = 0`.
  - Iterate through the string `s` from `i = 0` to `n-1`.
  - In each iteration, update `end` to be the maximum of its current value and the pre-computed last index of `s.charAt(i)`.
  - If the current index `i` is equal to `end`:
    - A partition is found. Add its length (`end - start + 1`) to `result`.
    - Update `start` to `i + 1` to mark the beginning of the next partition.
- Return the `result` list.

# Solutions
### CSharp

```csharp
public class Solution {
    public IList < int > PartitionLabels(string s) {
        int[] last = new int[26];
        int n = s.Length;
        for (int i = 0; i < n; i++) {
            last[s[i] - 'a'] = i;
        }
        IList < int > ans = new List < int > ();
        for (int i = 0, j = 0, mx = 0; i < n; ++i) {
            mx = Math.Max(mx, last[s[i] - 'a']);
            if (mx == i) {
                ans.Add(i - j + 1);
                j = i + 1;
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  List<Integer> partitionLabels(String s) {
    int[] last = new int[26];
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      last[s.charAt(i) - 'a'] = i;
    }
    List<Integer> ans = new ArrayList<>();
    int mx = 0, j = 0;
    for (int i = 0; i < n; ++i) {
      mx = Math.max(mx, last[s.charAt(i) - 'a']);
      if (mx == i) {
        ans.add(i - j + 1);
        j = i + 1;
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @return {number[]} */ var partitionLabels = function ( s ) { const last = new Array ( 26 ). fill ( 0 ); const idx = c => c . charCodeAt () - ' a ' . charCodeAt (); const n = s . length ; for ( let i = 0 ; i < n ; ++ i ) { last [ idx ( s [ i ])] = i ; } const ans = []; for ( let i = 0 , j = 0 , mx = 0 ; i < n ; ++ i ) { mx = Math . max ( mx , last [ idx ( s [ i ])]); if ( mx === i ) { ans . push ( i - j + 1 ); j = i + 1 ; } } return ans ; };
```

### CPP

```cpp
class Solution {
public:
  vector<int> partitionLabels(string s) {
    int last[26] = {0};
    int n = s.size();
    for (int i = 0; i < n; ++i) {
      last[s[i] - 'a'] = i;
    }
    vector<int> ans;
    int mx = 0, j = 0;
    for (int i = 0; i < n; ++i) {
      mx = max(mx, last[s[i] - 'a']);
      if (mx == i) {
        ans.push_back(i - j + 1);
        j = i + 1;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def partitionLabels(self, s: str) -> List[int]: last = {c: i for i, c in enumerate(s)} mx = j = 0 ans = [] for i, c in enumerate(s): mx = max(mx, last[c]) if mx == i: ans . append(i - j + 1) j = i + 1 return ans

```