JavaScript로 문자열에서 동일한 두 문자 사이의 가장 긴 부분 문자열 구하기

문제 소개

문자열을 유일한 인수로 받아 처리하는 자바스크립트 함수를 작성해야 합니다.

이 함수의 목표는 동일한 두 문자 사이에 끼어 있는 가장 긴 부분 문자열을 찾아 그 길이를 반환하는 것입니다.

문제 예시

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

const str = 'sadtrsewak';

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

const output = 6;

그 이유는 두 개의 문자 'a' 사이에 위치한 'dtrsew'가 조건을 만족하는 가장 긴 부분 문자열이며, 그 길이가 정확히 6이기 때문입니다.

해결 방법: 해시 맵 활용

이 문제는 각 문자가 처음 등장한 위치를 해시 맵(객체)에 기록해 두면 선형 시간 O(n) 안에 효율적으로 해결할 수 있습니다. 어떤 문자가 다시 등장하면 현재 인덱스에서 첫 등장 인덱스를 뺀 값에 1을 더 빼면, 그것이 곧 두 문자 사이의 부분 문자열 길이가 됩니다.

구현 코드

const str = 'sadtrsewak';
const longestSubstringBetween = (str = '') => {
    const map = {};
    let res = -1;
    for(let i = 0; i < str.length; i++){
        const el = str[i];
        if(map.hasOwnProperty(str[i])){
            res = Math.max(res, i - map[el] - 1);
        }else{
            map[el] = i;
        };
    };
    return res;
}
console.log(longestSubstringBetween(str));

코드 동작 원리

1. map 객체 생성: 각 문자가 처음 나타난 인덱스를 저장하는 역할을 합니다.
2. res 변수 초기화: 결과값을 -1로 설정하여, 동일한 문자 쌍이 하나도 없을 경우 -1을 반환하도록 합니다.
3. 반복문 처리: 문자열을 순회하면서 해당 문자가 map에 이미 존재하면 두 인덱스 사이의 거리(i - map[el] - 1)를 계산해 최댓값을 갱신하고, 존재하지 않으면 현재 인덱스를 map에 저장합니다.

실행 결과

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

6

인덱스 1의 'a'와 인덱스 8의 'a' 사이에 있는 부분 문자열 'dtrsew'의 길이인 6이 정확히 반환된 것을 확인할 수 있습니다.