Leetcode - Partition Labels
Tags: beginners
Published: 2020-08-15 21:52:30

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](https://leetcode.com/problems/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):

```javascript
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!