Leetcode - Partition Labels

As I've prepared for interviews Leetcode has been a place I've turned to often to brush up on logic questions and try to expand the way I approach problems.

I recently worked on a problem called Partition Labels that I felt was a good exercise in dissecting a problem and creating a plan of attack.

The problem provides a string and asks us to break up the string into as many partitions as possible where any letter appears in no more than one partition. It then asks us to return the length of each partition. The string cannot be sorted or reordered in any way.

For example:

partitionLabel('abcd') => [1,1,1,1]
partitionLabel('abcda') => [5]

The first example abcd returns the array [1,1,1,1] because each letter becomes its own partition. The second example, abcda, returns the array [5] because the last a in the given string does not allow for the creation of any partitions. This is because a also appears at the beginning of the string.

Knowing that any repeating letter would need to be combined with the first occurrence of that letter and all letters between, my goal was to loop through the length of the string and create partitions where a letter appeared that had not appeared in the string since the last partition was created (using a continually modified comparison index). I then had to consider what I would do if a letter reoccured when its past instances had already been sectioned off into their own partition. My solution was to compare a given letter to each partition that had been created. If a partition included the given letter, I would remove that partition and any others created after that. I would also need to reset my comparison index to an earlier point in the string. With this strategy, once I complete my loop I am able to create one additional partition for the last slice of the string (from the comparison index through the end). Lastly I return the array of partitions mapped to the length of each element.

Here is my code (in JS):

var partitionLabels = function (S) {
  let result = [];
  let ind = 0;
  for (let i = 1; i < S.length; i++) {
    if (S.slice(ind, i).includes(S[i])) {
      continue;
    } else {
      let isGood = true;
      for (let y = 0; y < result.length; y++) {
        if (result[y].includes(S[i])) {
          result.splice(y);
          ind = result.join('').length;
          isGood = false;
        }
      }
      if (isGood) {
        result.push(S.slice(ind, i));
        ind = i;
      }
    }
  }
  result.push(S.slice(ind));
  return result.map(x => x.length);
};

First I created a result array to hold each partition that is created. Next I create my comparison index variable called ind (initially set to 0). I then create a for loop to iterate through each character of the input string (starting from the second letter because the first letter does not need to be compared to anything). If the targeted portion of the string (since the last partition was added) does include S[i], we simply continue; if not, we set a variable called isGood to true (indicating that the creation of a new partition is valid). We then check if any previous partitions include S[i]. If one does, we remove each partition starting from that one (inclusive). We then reset the comparison index, ind, to the length of the joined elements of result (because the length represents when the problematic partition began) and set isGood to false (indicating that a new partition is no longer valid). If S[i] is not found in an earlier partition isGood is unchanged and remains true so we push a new slice of S into result (starting from ind and ending at i) and reset ind to i. When we exit our for loop we still need to add one partition (from ind through the end of the string). Lastly we return result mapped to the length of each element.

I enjoyed working through this problem because it forced me to think about a practical solution before typing any code. Look forward to working through more problems similar to this one!