LeetCode 763 - Partition Labels (Medium)

문제

LeetCode - 763번

풀이 과정

투 포인터 와 그리디 알고리즘 을 사용하는 문제입니다.

partition 이 특정 문자들의 집합으로 이루어져 있을 때
가장 많은 partition 으로 나누기 위해서는 우선 다음과 같이 생각해볼 수 있습니다.

먼저 partition A 의 가장 첫 문자가 a 라고 한다면,
해당 partition 에는 문자열 S 에 존재하는 모든 a 를 포함해야합니다.

따라서 문자열 S 에서 가장 마지막에 존재하는 a 를 포함해야합니다.
그러므로 partition 의 기준이 되는 포인터 right 와
각 partition 의 문자들을 검사하기 위한 포인터 left 를 선언해서 탐색을 수행하면 됩니다.

코드

/**
 * @param {string} S
 * @return {number[]}
 */
var partitionLabels = function (S) {
  const answer = [];
  let left = 0;

  while (left < S.length) {
    let start = left;
    let right = S.lastIndexOf(S[left]);

    while (left < right) {
      right = Math.max(right, S.lastIndexOf(S[left++]));
    }
    left++;
    answer.push(right - start + 1);
  }

  return answer;
};