[LeetCode] Longest Substring without Repeating Characters

문제링크

Longest Substring Without Repeating Characters - LeetCode

 

 

주어진 문자열(s)의 subString의 길이를 구하는 문제이다.
이때 subString은 중복되는 문자가 없어야 한다.

접근방법

문자열 s을 순회하며 조건에 따라 subStrArr에 담는 방식으로 진행하였다.

조건1. 만약 subStrArr에 s의 문자(s[i])가 존재한다면 (subStrArr.includes(s[i]) === true) 문자가 없어질때까지 subStrArr의 앞에서부터 지운다. (shift)
조건2. 만약 subStrArr에 s의 문자(s[i])가 존재하지 않는다면 subStrArr에 s[i]를 push한다.

그런데 shift는 배열을 삭제할때마다 array의 index를 처음부터 다시 지정하는 O(n)의 비효율적인 방식이다.

그래서 이를 고민하다.. 다른 분의 풀이는 어떤지 살펴보았다.

굳이 배열로 만들지 않고 substring 메서드를 사용하여 문자열을 자른 코드를 발견하였다.

핵심 내용은 새로 만든 subStr의 subStr.indexOf(s[i])를 검사해서
만약 있으면 subStr.indexOf(s[i]) +1 (0부터 시작하므로) 부터 잘라 새로운 subStr을 만들고
없다면 s[i]를 더하는 식으로 진행한다.

 

// 나의 풀이

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let maxLength = 0;
  let subStrArr = [];
  for (let i = 0; i < s.length; i++) {
    if (!subStrArr.includes(s[i])) subStrArr.push(s[i]);
    else {
      while (subStrArr.includes(s[i])) {
        subStrArr.shift();
      }
      subStrArr.push(s[i]);
    }
    maxLength = Math.max(maxLength, subStrArr.length);
  }
  return maxLength;
};

// 효율적인 풀이

// 주어진 문자열 s의 subStirng을 구하는 문제
// subString의 조건은 중복되는 문자가 없어야한다.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let maxLength = 0;
  let subStr = '';

  for (let i = 0; i < s.length; i++) {
    subStr = subStr.substring(subStr.indexOf(s[i]) + 1);
    subStr += s[i];

    if (subStr.length > maxLength) maxLength = subStr.length;
  }

  return maxLength;
};