Study Log

20200529 리트코드

Longest Substring Without Repeating Characters

중복된 문자 없이 가~~장 긴 Substring을 구하는 문제이다.

var lengthOfLongestSubstring = function (str) {
    let s = 0
    let res = 0
    const m = new Map()
    for (let i = 0; i < str.length; i++) {
      if (m.has(str[i]) && m.get(str[i]) >= s) {
        res = Math.max(res, i - s)
        s = m.get(str[i]) + 1
      }
      m.set(str[i], i)
    }
    return Math.max(res, str.length - s)
  };
  console.log(lengthOfLongestSubstring("ab"))

시간복잡도

O(n)

아이디어

문자의 인덱스를 해시에 저장하여 불필요한 연산을 줄인다.

실수 했던 부분들

  1. 만약 Map 에 저장된 index가 0 이라면 if(m.get(str[i])) 를 했을 때 0은 falthy한 값이기 때문에 false가 나온다 ( 해시에 저장된 값이여도 )

  2. 반복문 안 조건문으로 특정값을 갱신할 때 마지막 값을 반복문이 끝나고 조건에 부합하는지 한번 더 체크해야 했다

    for (...) {
 if (...)
 ...//update
}
// 마지막 값이 조건에 부합하는지 체크
Written by@[HongDongUk]
공부한 것을 소소하게 적는 블로그.

GitHubFacebook