[알고리즘 - LeetCode] Longest Substring Without Repeating Characters

김혜진·2019년 12월 1일

algorithms

목록 보기

6/8

문제

Given a string, find the length of the longest substring without repeating characters.
주어진 문자열에서 알파벳이 중복되지 않고 가장 길게 연속되는 문자열 일부를 반환하라

Example 1:

Input: "abcabcbb"
Output: 3 

Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"
Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3

Explanation: The answer is "wke", with the length of 3. 
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

풀이

리트코드에서 처음으로 푼 Medium 레벨.
지문과 예제들이 간단해서 몇 줄 코드로 풀 문제인줄 알았는데.. 허허.. 쌓여가는 조건문들.. 허허

제출 코드

const lengthOfLongestSubstring = function(s) {
    if (!s) return 0;
    
    let check = '';
    const result = [];
    
    for (let i = 0; i < s.length; i++) {
        if (check[check.length - 1] !== s[i] && !check.includes(s[i])) {
            check += s[i];
        } else {
            if (check[check.length - 1] === s[i]) {
                result.push(check.length);
                check = s[i];
            } else {
                result.push(check.length);
                check = check.slice(check.indexOf(s[i]) + 1);
                i--;
            }
        }
    }
    if (check) result.push(check.length);
    
    return Math.max(...result);
};

문자열을 순회하며
양 옆의 알파벳 2개가 다르고 && 이미 확인한 문자들중 같은 알파벳이 존재하는지 확인하여
통과시 check 변수 값에 문자를 더해주고
그렇지 않을 시
4-1. 양 옆의 알파벳이 같은 경우에는 현재까지 확인한 check값의 길이를 배열에 담고 해당 알파벳을 check 값으로 재할당하고
4-2. check 변수에 같은 알파벳이 존재하는 경우에는 해당 알파벳을 제외하고 나머지 연속되는 문자열을 check값으로 재할당한다.
모두 순회한 후 마지막 check값의 길이를 배열에 담은 후
가장 큰 값을 반환하다.

타 코드와 실행 속도 비교

easy 레벨보다 훨씬 극과 극을 달리는 듯한 결과. 문자열 순회를 한다는 공통 사항을 빼고는 정말 다양한 코드들이 있었다.

개선 사항

개인적으로 가독성이 높고 깔끔했던 코드

const lengthOfLongestSubstring = function(s) {
    let subStr = "";
    let maxLength = 0;
  
    for (let i = 0; i < s.length; i++) {
        if (subStr.includes(s[i])) {
            subStr = subStr.slice(subStr.indexOf(s[i]) + 1);
        }
        subStr += s[i];
        if (maxLength < subStr.length) {
            maxLength = subStr.length;
        }
    }
    return maxLength;
};

먼저 확인한 문자열들을 subStr 변수에 담아
중복되는 알파벳이 있는지 체크하여 subStr을 재할당하고
연속되는 문자열의 길이를 새로 확인하는 문자열의 길이와 지속적으로 비교하여 더 큰 값을 maxLength 변수에 할당하고
문자열 순회를 마친 후 maxLength반환

includes, indexOf, slice등을 사용하여 연속 문자열 길이를 확인하는 것이 문제 접근 방식은 내 코드와 크게 다르지 않은데 훨씬 핵심만을 담백하게 파악한 코드이다.
그러니까 양 옆의 알파벳이 같다는 것은 결국 먼저 확인한 문자열 안에 동일한 알파벳이 있다는 것과 같은 말이다...

변경 후 코드

const lengthOfLongestSubstring = function(s) {
    if (!s) return 0;
    
    let check = '';
    const result = [];
    
    for (let i = 0; i < s.length; i++) {
        if (check.includes(s[i])) {
            check = check.slice(check.indexOf(s[i]) + 1);
        }
      
        check += s[i];
        result.push(check.length);
    }
    
    return Math.max(...result);
};