JavaScript에서 고유한 문자가 정확히 하나인 부분 문자열 개수 세기

문자열을 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수의 과제는 입력 문자열에서 고유한 문자가 정확히 하나뿐인 연속된 부분 문자열을 모두 찾아 개수를 세는 것입니다.

함수는 조건을 만족하는 부분 문자열의 총 개수를 반환해야 합니다.

예시

예를 들어, 입력 문자열이 다음과 같다고 가정해 보겠습니다.

const str = 'iiiji';

이때 기대하는 출력은 다음과 같습니다.

const output = 8;

그 이유는 조건에 맞는 문자열이 다음과 같기 때문입니다.

'iii', 'i', 'i', 'i', 'i', 'j', 'ii', 'ii'

접근 방식

이 문제는 문자열을 한 번만 순회하는 O(n) 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 각 단일 문자 자체도 유효한 부분 문자열이므로, 먼저 결과값을 문자열의 길이로 초기화합니다. 빈 문자열이라면 0을 그대로 반환합니다.
• 두 개의 포인터를 사용합니다. i는 현재 위치를, j는 지금까지 이어진 동일 문자 구간(run)의 시작 위치를 가리킵니다.
• str[i]와 str[j]가 같다면 현재 구간이 계속 이어지는 것이므로, i 위치에서 끝나는 새로운 유효 부분 문자열의 개수(i − j개)를 결과에 더합니다.
• 두 문자가 다르다면 새로운 구간이 시작된 것이므로 j를 i로 갱신합니다.

코드

다음은 위 로직을 구현한 코드입니다.

const str = 'iiiji';
const countSpecialStrings = (str = '') => {
    let { length } = str;
    let res = length;
    if (!length) {
        return length;
    };
    for (let j = 0, i = 1; i < length; ++i) {
        if (str[i] === str[j]) {
            res += i - j;
        } else {
            j = i;
        }
    };
    return res;
}
console.log(countSpecialStrings(str));

출력

다음은 콘솔 출력 결과입니다.

8

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다. 중첩 반복문으로 모든 부분 문자열을 검사하는 비효율적인 방법과 달리, 선형 시간에 답을 구할 수 있다는 점이 큰 장점입니다.