1133. Last Substring in Lexicographical Order

리트코드 1133번 풀이

문제

Last Substring in Lexicographical Order

풀이

아이디어

답은 항상 어떤 인덱스 i에서 끝까지의 suffix s[i:]이다. (같은 시작 지점의 부분 문자열 중 가장 긴 것이 사전순으로 크거나 같기 때문)

따라서 두 포인터 i, j로 현재 가장 유력한 후보 suffix를 비교한다. k만큼 앞부분이 같다면 아래 세 가지로 분기한다.

1. j + k가 끝에 도달 → s[j:]는 s[i:]보다 작거나 같음 → j를 k+1 앞으로 스킵
2. s[j+k] > s[i+k] → j가 더 큰 후보 → i를 max(j, i+k)로 업데이트
3. s[i+k] > s[j+k] → i가 더 큼 → j를 k+1 앞으로 스킵

놓쳤던 부분

계속 오답과 시간 초과와 싸웠었는데… 몇가지 놓친 부분이 있었기 때문이다.

우선 시간 초과 해결의 핵심은 O(n)을 만드는 것이었다! 처음엔 j를 업데이트해야 할 떄 j++ 로 업데이트했었고 시간초과가 계속 발생했었다.ㅠㅠ 알고 보니 분기를 도는 과정에서 k길이까지는 i, j가 같은 부분임을 확인했기 때문에 k길이까지는 다시 비교할 필요가 없었던 것이었다. 그래서 j += k + 1로 업데이트하니 O(n)의 시간복잡도를 가질 수 있었고 시간 초과가 해결되었다.

오답은… i를 업데이트하는 부분에 문제가 있었기 때문이었다. i를 업데이트해야 하는 첫번째 분기에서, j가 i보다 크기 때문에 무조건 i = j로 업데이트하면 되겠다고 생각했었다. 하지만 앞선 반복에서 계속 겹치는 부분을 넘겼기 때문에 "cacacb"를 예로 들었을 때 i=0, j=2, k=3일 때 s[0:3] == s[2:5]라는 게 이미 확정된 상태. 이 말은 i와 j의 suffix가 겹쳐있다는 뜻이고, 단순히 i = j = 2로 옮기면 s[3:] 이후의 후보들을 올바르게 비교하지 못한다.

i + k까지의 구간은 이미 s[i:]와 동일하다는 게 확정됐으니까, 새 i는 최소한 i + k 이상이어야 한다. 동시에 j보다는 작을 수 없으니까 Math.max(j, i + k)가 된다. 그래서 단순히 i = j로 업데이트하는 게 아니라 i = Math.max(j, i + k)로 업데이트해야 한다.

코드

function lastSubstring(s: string): string {
  let i = 0,
    j = 1;

  while (j < s.length) {
    let k = 0;
    while (j + k < s.length && i + k < s.length && s[i + k] === s[j + k]) {
      k++;
    }

    if (j + k === s.length) {
      j += k + 1;
    } else if (s[i + k] < s[j + k]) {
      const nextI = Math.max(j, i + k);
      i = nextI;
      j = i + 1;
    } else {
      j += k + 1;
    }
  }

  return s.substring(i);
}

시간 / 공간 복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)