자바스크립트로 두 개의 동일한 문자 사이에서 가장 긴 부분 문자열 찾기

문자열을 인수로 받아 두 개의 동일한 문자 사이에 끼어 있는 가장 긴 부분 문자열의 길이를 찾아 반환하는 자바스크립트 함수를 작성해야 합니다.

문제 이해하기

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

const str = 'avbghvh';

이 경우 기대되는 출력은 다음과 같습니다.

const output = 3;

그 이유는 가장 긴 부분 문자열이 두 개의 'v' 사이에 위치한 'bgh'이며, 그 길이가 정확히 3이기 때문입니다.

해결 접근 방식

이 문제는 해시 맵(Map) 객체를 활용하면 선형 시간 안에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 각 문자가 처음 등장한 인덱스를 Map 객체에 저장합니다.
• 순회 중 이미 저장된 문자를 다시 만나면, 두 인덱스 사이의 거리(현재 인덱스 − 첫 등장 인덱스 − 1)가 해당 문자 쌍 사이의 부분 문자열 길이가 됩니다.
• 매번 최대값(max)을 갱신하여 순회가 끝난 후 반환합니다.

예제 코드

const str = 'avbghvh';
const longestSub = (str = '') => {
    const map = new Map();
    let max = -1;
    for(let i = 0; i < str.length; i++){
        if(map.has(str.charAt(i))){
            max = Math.max(max, i - map.get(str.charAt(i)) - 1);
        }else{
            map.set(str.charAt(i), i);
        };
    };
    return max;
};
console.log(longestSub(str));

코드 설명

위 코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

1. 빈 Map 객체와 초기값이 -1인 max 변수를 생성합니다. -1은 동일한 문자 쌍이 하나도 존재하지 않을 때 반환되는 기본값입니다.
2. 문자열을 처음부터 끝까지 순회하면서 각 문자가 Map에 없으면 현재 인덱스를 저장합니다.
3. 이미 존재하는 문자라면 두 인덱스의 차이에서 1을 빼 그 사이에 있는 문자 개수를 구하고, 기존 max보다 크면 값을 갱신합니다.

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

3

복잡도 분석

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 각 고유 문자를 Map에 저장하므로 공간 복잡도 역시 O(n)입니다. 덕분에 문자열 길이가 길어져도 효율적으로 동작합니다.