JavaScript로 무한 순환 문자열에서 고유한 부분 문자열 개수 구하기

문제 이해하기

문자열 "abcdefghijklmnopqrstuvwxyz"를 끝없이 반복해서 이어 붙인 무한 순환 문자열 S가 있다고 가정해 봅시다. 그러면 S는 다음과 같은 형태가 됩니다.

"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."

우리가 작성해야 할 JavaScript 함수는 임의의 문자열 str을 인수로 하나 받아서 다음을 수행해야 합니다.

str의 비어 있지 않은 부분 문자열 중에서 S에 실제로 존재하는 것들을 찾습니다.
이때 서로 다른(고유한) 부분 문자열의 개수를 최종적으로 반환합니다.

예시

입력이 다음과 같다고 해보겠습니다.

const str = "zab";

그렇다면 기대하는 출력은 다음과 같습니다.

const output = 6;

출력 설명

문자열 "zab"의 부분 문자열 중 S에 포함되는 것은 "z", "a", "b", "za", "ab", "zab"으로 총 6개입니다. 따라서 정답은 6이 됩니다.

접근 방법: 동적 계획법(DP)

모든 부분 문자열을 직접 나열하면 시간 복잡도가 급격히 커지므로, 동적 계획법을 활용하는 것이 효율적입니다.

핵심 아이디어는 다음과 같습니다.

S에서 연속된 알파벳으로 이루어진 부분 문자열만 유효합니다. 즉, 각 문자가 이전 문자보다 정확히 1씩 크거나(예: a→b), 'z'에서 'a'로 넘어가는 경우(-25 차이)여야 합니다.
길이가 k인 유효 부분 문자열은 항상 길이 1부터 k까지의 모든 하위 부분 문자열을 포함합니다.
따라서 각 알파벳별로 '해당 문자로 끝나는 가장 긴 유효 부분 문자열의 길이'를 저장하면, 그 값 자체가 해당 문자로 끝나는 고유 부분 문자열의 개수와 같습니다.

dp 배열의 크기를 26으로 두고, 각 위치에서 현재 문자로 끝나는 최대 연속 길이를 갱신한 뒤 마지막에 모두 더하면 정답을 얻을 수 있습니다.

구현 코드

const str = "zab";
const allSubstrings = (str = '') => {
   const dp = new Array(26).fill(0);
   dp[str.charCodeAt(0) - 97] = 1;
   let maxCount = 1;
   for (let i = 1; i < str.length; i++) {
      if ((str.charCodeAt(i) - str.charCodeAt(i - 1) == 1) || (str.charCodeAt(i) - str.charCodeAt(i - 1) == -25)) {
         maxCount++;
      } else {
         maxCount = 1;
      }
      dp[str.charCodeAt(i) - 97] = Math.max(dp[str.charCodeAt(i) - 97], maxCount);
   }
   return dp.reduce((item, val) => {
      return val + item;
   })
};
console.log(allSubstrings(str));

코드 설명

dp 배열: 인덱스 0~25가 각각 'a'~'z'에 대응하며, 해당 문자로 끝나는 고유 부분 문자열의 최대 개수를 저장합니다.
maxCount: 현재 위치까지 이어지는 연속 알파벳 시퀀스의 길이를 추적합니다. 인접한 두 문자의 차이가 1이거나 z→a 전환(-25)이면 1 증가하고, 그렇지 않으면 1로 초기화됩니다.
Math.max 갱신: 같은 문자로 끝나는 여러 시퀀스가 있을 수 있으므로, 항상 더 긴 값을 유지합니다. 이렇게 하면 중복 없이 고유한 부분 문자열만 정확히 셀 수 있습니다.
reduce 합산: 마지막에 dp 배열의 모든 값을 더해 전체 고유 부분 문자열 개수를 반환합니다.

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

이 알고리즘은 문자열의 길이 n에 대해 O(n)의 시간 복잡도와 O(1)의 공간 복잡도(고정 크기 26 배열)로 동작하므로 매우 효율적입니다.