JavaScript로 문자열에서 연속 반복되는 최대 문자 개수 구하는 방법

다음과 같이 반복되는 문자가 포함된 문자열이 있다고 가정해 보겠습니다.

const a = "fdsfjngjkdsfhhhhhhhhhhhfsdfsd";

우리가 작성해야 할 함수는 문자열에서 같은 문자가 연속으로 나타나는 최대 횟수를 반환하는 함수입니다. 위 문자열에서는 문자 'h'가 연속으로 11번 나타나기 때문에, 이 문자열에 대해 함수는 11을 반환해야 합니다.

슬라이딩 윈도우(Sliding Window) 알고리즘 접근법

이 문제는 슬라이딩 윈도우 알고리즘을 적용하기에 아주 적합한 유형입니다. 여기서 '안정적인(stable) 윈도우'란 동일한 문자만 연속적으로 포함된 구간을 의미하고, 서로 다른 문자가 섞여 있는 구간은 '불안정한(unstable) 윈도우'라고 볼 수 있습니다. 윈도우는 끝 부분에 새로운 문자를 추가하고, 시작 부분의 중복되지 않는 지점을 제거하면서 안정적인 상태를 유지해 나갑니다.

예제 코드

슬라이딩 윈도우 알고리즘을 활용한 함수의 전체 코드는 다음과 같습니다.

const a = "fdsfjngjkdsfhhhhhhhhhhhfsdfsd";
const findMaximumRepeating = str => {
   let max = 0;
   for(let start = 0, end = 1; end < str.length; ){
      if(str[end] === str[start]){
         if(max < end - start + 1){
            max = end - start + 1;
         };
         end++;
      } else {
         start = end;
      };
   };
   return max;
};
console.log(findMaximumRepeating(a));

코드 동작 원리

start와 end 두 개의 포인터를 사용하여 현재 연속 구간(윈도우)을 추적합니다.
str[end]가 str[start]와 같다면 같은 문자가 계속 이어지고 있는 것이므로, 현재 구간의 길이(end - start + 1)가 기존 최댓값보다 클 경우 max를 갱신하고 end를 한 칸 앞으로 이동시킵니다.
두 문자가 다르다면 새로운 연속 구간이 시작된 것이므로, start를 end 위치로 이동시켜 새로운 윈도우를 만듭니다.
문자열의 모든 문자를 확인한 후 최종적으로 max 값을 반환합니다.

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)으로 매우 효율적입니다.

실행 결과

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