[Algorithm] [중급] 반복없는 가장 긴 substring 의 길이 구하기

오늘은 String 내에서 반복이 없는 가장 긴 Substring의 길이 구하는 법에 대해 알아보도록 하겠습니다.

문제

String인 s 변수가 함수의 파라미터로 주어질 때 s의 substring 중 가장 긴 substring의 길이를 구하는 문제입니다. 예를 들면

Input: "abcabcbb"
Output: 3
Input: "bbbbb"
Output: 1
Input: "pwwkew"
Output: 3

이런 식의 답이 나오면 되겠습니다.

풀이

어떤 알고리즘 문제든 그렇듯이 모든 가능성을 전부 구한 다음에 가장 긴 String을 찾으려고 하시면 안 됩니다. 방법은 substring의 시작 부분과 끝부분 인덱스를 변수로 지정하여 j를 1씩 올리다 현재 substring에 존재하는 문자가 나오면 i를 올리는 식으로 진행하면서 string.length까지 반복하시면 됩니다. 예제는 아래와 같이 되겠습니다.

const longerWay = function (s) {
    const length = s.length;
    const set = new Set();

    // substring 윈도우의 왼쪽끝
    let i = 0;
    // substring 윈도우의 오른쪽끝
    let j = 0;
    let longest = 0;

    while (i < length && j < length) {
        const endChar = s[j];

        if (!set.has(endChar)) {
            // 캐릭터가 없을경우 세트에 추가해주고 가장 긴 길이를 갱신
            set.add(s[j++]);
            longest = Math.max(longest, j - i);
        } else {
            // 캐릭터가 있을경우 세트에서 substring 윈도우의 왼쪽 끝 캐릭터 삭제
            set.delete(s[i++]);
        }
    }

    return longest;
};

위와 같이 풀게 되면 최악의 경우 O(2n)의 시간이 걸려 전체 리스트를 2번 보게 됩니다. 살짝 더 알고리즘을 최적화해서 O(n)의 퍼포먼스를 보일 수 있는데, 그 방법은 이미 지나간 캐릭터와 인덱스를 Map에 저장해두고 j를 이동시키며 똑같은 캐릭터를 만날 시 미리 Map에 저장해둔 최근 본 동일 캐릭터의 index + 1로 i를 이동시키는 겁니다. 예제는 아래와 같습니다.

const shorterWay = function (s) {
    const length = s.length;

    const map = {};
    let longest = 0;

    // substring 윈도우의 왼쪽끝
    let i = 0;
    // substring 윈도우의 오른쪽끝
    let j = 0;

    while (j < length) {
        
        const endChar = s[j];

        // Map에 substring의 오른쪽 끝 캐릭터가 이미 저장되어있을경우
        // 해당 캐릭터의 인덱스 + 1 만큼 i 인덱스를 이동시킵니다.
        if (map[endChar]) {
            i = Math.max(map[endChar], i);
        }

        longest = Math.max(longest, j - i + 1);
        map[endChar] = j + 1;

        j++;
    }

    return longest;
};

위와 같이 작업할 경우 O(n) 퍼포먼스를 보일 수 있어 보다 빠르게 프로그램 실행이 가능합니다.

문제는 아래 링크를 참조하였습니다.

LeetCode