[LeetCode] Longest Substring Without Repeating Characters (javascript)

가장 긴 반복되지 않는 문자열의 길이를 리턴하는 문제다.

 

예를들어

abcdaddd => [abcd][ad][d][d] = 4

abcabc => [abc][abc] = 3

 

처음엔 문자별로 for문을 돌면서

다음에 출현하는 같은 문자까지의 index 차이를 구하려고 했다.

abcabc => [abc] "a"bc => 3

 

다만 이런경우...

abbabc => [abb] "a"bc => 3 이런 케이스를 피할 수 없고,

또 abb안에서 중복이 없는지 검사하는 등 복잡해지게 된다.

 

다른 풀이들을 참고한 결과,

substring해가면서 중복이 없으면 결과값에 더해주고, 중복이 있으면 앞글자를 방출하는 형태가

가장 이해하기도 편하고 코드도 깔끔해 보여서 이렇게 구현했다.

 

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    if (s.length < 2) return s.length;

    let current = '';
    let maxLen = 0;
    for (let i = 0; i < s.length; i++) {
        // 구해낸 길이가 반 이상이면 바로 리턴하도록 해보고싶었으나..
        // substring(이상[, 미만])
        // - 존재하지 않으면 0이 되어 substring되지 않음.
        // - 존재하면 abcd + a 의 상황에서 a를 잘라낸 bcd + a를 해줌
        current = current.substring(current.indexOf(s[i]) + 1);
        current += s[i];

        if (current.length > maxLen) maxLen = current.length;
    }
    return maxLen;
};

 

다만 이렇게 푸는 경우, 가장 긴 길이를 리턴하는 것이 아니라

모든 경우의 수를 리턴하라거나, 가장 긴 길이를 가진 문자열을 모두 리턴하라고 하면 다른 방법을 생각해야 한다.

 

https://leetcode.com/problems/longest-substring-without-repeating-characters/