[Leetcode - String] Longest substring without repeating characters 풀이

 

 

문제 링크

 

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

 

---

풀이

이 문제는 문자열에서 중복 없이 가장 긴 substring의 길이를 반환하는 문제이다. 내가 접근한 방식은 완전 탐색이다.

자신보다 뒤에 있는 문자열들을 순회하면서 중복이 발생하기 전까지의 길이를 찾아 저장해놓은 max length와 비교하는 로직을 작성했다.

O(N^2)의 시간 복잡도를 가지기 때문에 상대적으로 너무 느리다.

 

다른 사람들의 풀이를 보았고, O(N)으로 푸는 코드를 찾았다.

이 코드는 각 문자열을 map이라는 객체에 저장하면서 value로 이 문자가 가장 마지막으로 나온 index를 저장한다. 이로 인해 한번 순회로 중복 없는 최대 길이를 구할 수 있다.

 

 

 

---

정답 코드

 

var lengthOfLongestSubstring = function (s) {
  let maxLen = 0;
  let tempLen = 0;
  let arr = [...s];
  let arrLen = arr.length;
  let obj = {};
  for(let i=0; i<arrLen; i++) {
    obj = {};
    tempLen = 0;
    for(let j=i; j<arrLen; j++) {
      if(obj[arr[j]]) break;
      else {
        tempLen += 1;
        obj[arr[j]] = true;
      }
    }
    maxLen = Math.max(maxLen, tempLen);
  }
  return maxLen;
};

 

 

---

O(N) code

 

function lengthOfLongestSubstringBest(s) {
  const map = {};
  var left = 0;

  return s.split('').reduce((max, v, i) => {
    left = map[v] >= left ? map[v] + 1 : left;
    map[v] = i;
    return Math.max(max, i - left + 1);
  }, 0);
}