763. Partition Labels

문제링크: https://leetcode.com/problems/partition-labels/

문자열을 최대한 나누되 같은 문자는 같은 구역에 존재하도록 하는 partition을 구하는 문제다.

Solution

1. Greedy with index map

문자열을 처음부분부터 최대한 한 구역에 포함시키는 쪽으로 접근하였다. ababcbacadefegdehijhklij 의 경우 처음에 a가 포함된 부분을 포함해 문제의 조건을 만족(같은 문자는 한 구역에 있어야 한다)하기 위해선 마지막 a가 있는 곳까지 포함시켜야한다. a가 있는 곳까지 탐색하는 중간에 b와 c를 만나는 경우 이 또한 마지막 b와 c를 포함시키는 구간까지 와야한다. 따라서 어떤 문자를 만났을 경우에 그 문자가 마지막으로 존재하는 index를 알아야하며 이를 처음에 한번 O(n)의 탐색을 통해 HashTable로 만들 수 있다.

이후 다시 처음으로 돌아가 한 구간을 최소한으로 정의하기 위해 같은 문자를 포함하는 index까지 탐색하고나면 가장 작은 분할 구역을 greedy하게 얻을 수 있고 이 방식을 반복하면 결과를 얻을 수 있다.

Algorithm

• 먼저 해당 문자의 마지막 index를 저장하는 indexMap을 만든다.
• 문자열을 순회하며 문자가 등장할 경우 자신의 최대 좌표를 갱신하는 식으로 indexMap을 완성한다.
• start는 구역이 시작하는 곳 -1, end는 구역이 끝나는 곳이다.
• 처음부터 탐색해 문자를 만나면 indexMap을 통해 end를 갱신한다.(최소한 end까지는 한 구역에 포함되어야 한다)
• end === i 인 경우 가장 작은 한 구역이 완성된 것으로 그 크기를 end - start로 구해 result에 추가하고 start를 i로 갱신한다.(다음 구역의 시작위치 -1)
• 위 과정을 끝까지 반복하고 result를 반환한다.

var partitionLabels = function(s) {
  // 문자가 중복되지 않도록 최대로 나누기
  // greedy with map
  const indexMap = {}; // letter => maxIndex
  for (let i = 0; i < s.length; i++) {
    indexMap[s[i]] = i;
  }
  
  const result = [];
  let start = -1;
  let end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, indexMap[s[i]]);
    if (end === i) {
      result.push(end - start);
      start = i;
    }
  }
  return result;
};

indexMap을 만드는데 O(n), greedy하게 구역을 나누는데 O(n) 총 O(n)의 시간복잡도가 필요하고 문자의 개수는 최대 26개로 O(1)의 공간복잡도가 필요하다.

2. Index map optimized

1번 방식의 indexMap을 charCode - 97 => last index 로 매핑시킨 26사이즈 배열로 조금 업그레이드 할 수 있다.

var partitionLabels = function(s) {
  // 문자가 중복되지 않도록 최대로 나누기
  // Greedy with map
  const indexMap = [];	// letter code - 97 => last index
  for (let i = 0; i < s.length; i++) {
    indexMap[s.charCodeAt(i) - 97] = i;
  }
  const result = [];
  let start = -1;
  let end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, indexMap[s.charCodeAt(i) - 97]);
    if (end === i) {
      result.push(end - start);
      start = i;
    }
  }
  return result;
};