763. Partition Labels

Description

The partitionLabels function takes a string s and partitions it into as many parts as possible so that each letter appears in at most one part. It returns a list of integers representing the size of these parts.

Intuition

To solve this problem, we need to keep track of the last occurrence of each character in the string. By knowing the last index of each character, we can ensure that a character does not appear outside of its partition.

Approach

1. Create a dictionary to store the last occurrence of each character: Iterate through the string s and populate the lastIdx dictionary with the index of the last occurrence of each character.
2. Initialize variables: Create a list res to store the lengths of the partitions, and two variables curLast and accu to track the current end of the partition and the starting index of the next partition, respectively.
3. Iterate through the string: For each character in the string, update curLast to be the maximum of its current value and the last occurrence of the current character.
4. Partition the string: When the current index equals curLast, it means the current partition ends here. Append the length of the partition to res and update accu to be the index of the next character.
5. Return the result: The res list will contain the lengths of all partitions.

Complexity

Time Complexity:

O(n), where n is the length of the string. We iterate through the string twice: once to create the lastIdx dictionary and once to partition the string.

Space Complexity:

O(1) for the res list and lastIdx dictionary, as the size of the dictionary is bounded by the number of unique characters (which is constant, 26 in the case of lowercase English letters).

Code

C++

class Solution {
public:
    std::vector partitionLabels(std::string s) {
        std::unordered_map lastIdx;
        for (int i = 0; i < s.length(); i++) {
            lastIdx[s[i]] = i;
        }

        int curLast = 0, accu = 0;
        std::vector res;
        for (int i = 0; i < s.length(); i++) {
            curLast = std::max(curLast, lastIdx[s[i]]);
            if (i == curLast) {
                res.push_back(i + 1 - accu);
                accu = i + 1;
            }
        }
        return res;
    }
};

Python

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        lastIdx = {char: idx for idx, char in enumerate(s)}
        
        res = []
        curLast, accu = 0, 0
        
        for i, char in enumerate(s):
            curLast = max(curLast, lastIdx[char])
            if i == curLast:
                res.append(i + 1 - accu)
                accu = i + 1
        
        return res

Java

class Solution {
    public List partitionLabels(String s) {
        Map lastIdx = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            lastIdx.put(s.charAt(i), i);
        }
        List res = new ArrayList<>();
        int curLast = 0, accu = 0;
        for (int i = 0; i < s.length(); i++) {
            curLast = Math.max(curLast, lastIdx.get(s.charAt(i)));
            if (i == curLast) {
                res.add(i + 1 - accu);
                accu = i + 1;
            }
        }
        return res;
    }
}

JavaScript

/**
 * @param {string} s
 * @return {number[]}
 */

    var partitionLabels = function (s, lastIdx = {}) {

  for (let i = 0; i < s.length; i++) {
    lastIdx[s[i]] = i;
  }
  
  let curLast = 0, res = [], accu = 0;
  for (let i = 0; i < s.length; i++) {
    curLast = Math.max(curLast, lastIdx[s[i]]);
    if (i === curLast) {
      res.push(i + 1 - accu);
      accu = i + 1;
    }
  }
  return res;
};