Leetcode problem 69 - Partition Labels

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.

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]

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function (s) {
  // create a result array to store the size of each partition
  let result = [];
  // create a hash table to store the last index of each letter
  let hash = {};

  // Find last index of each letter and store in hash table
  for (let i = 0; i < s.length; i++) {
    // store the last index of each letter
    hash[s[i]] = i;
  }

  // create an end variable to store the end index of each partition
  let end = 0;
  // create a size variable to store the size of each partition
  let size = 0;
  // Find last index of each letter
  for (let i = 0; i < s.length; i++) {
    // increment the size of each partition
    size += 1;

    // if the last index of each letter is greater than the end index of each partition
    if (hash[s[i]] > end) {
      // update the end index of each partition
      end = hash[s[i]];
    }

    // if the current index is equal to the end index of each partition
    if (i === end) {
      // push the size of each partition to the result array
      result.push(size);
      // reset the size of each partition
      size = 0;
    }
  }
  // return the result array
  return result;
};

The time complexity of the partitionLabels function is O(n), where n represents the length of the input string s. It consists of two linear passes through the string. The first pass constructs a hash table that stores the last index of each character, taking O(n) time. The second pass determines the partition sizes while keeping track of the end index of each partition. Thus, the overall time complexity is O(n), making it an efficient solution for partitioning the input string into parts with unique characters.