[Leetcode] Longest Substring Without Repeating Characters

Hyodduru ·2022년 3월 19일
0

Algorithm

목록 보기
18/25
post-thumbnail

내가 생각한 로직

▪️ max = 중복되지 않은 알파벳으로 이루어진 제일 긴 단어의 길이 (cnt의 최대값)
▪️ s = 중복되지 않은 알파벳으로 이루어진 단어
▪️ cnt = s의 길이

  1. 파라미터로 받은 str 이라는 문자열을 for of를 돌리며, str의 단어 중 s라는 문자열에 포함된 것인지 탐색한다.

  2. if 포함하지 않는다면 👉 cnt counting, s에 해당 단어 추가
    이미 포함하고 있다면, 중복이 된 것이므로 👉 cnt =1, s는 해당 단어 값으로 지정하여 기존의 값을 더해왔던 것들을 다 reset해준다.

그런데 이게 앞에서만 for문을 돌릴 경우, 잡지 못하는 경우의 수도 존재한다.

예를 들어 str이 abcaxyzef인 경우 위의 for문을 돌릴 시, s는 xyzef, max는 6이 return이 되지만 사실 가장 긴 문자열은 bcaxyzef이다.

이런 경우에 일어날 수 있는 오류를 방지하기 위해 거꾸로도 for문을 돌려주어야한다.

해당 풀이는 아래와 같다.

const getLengthOfStr = str => {
let max = 0;
  let cnt = 0;
  let s = ""
  for(let x of str){
    if(!s.includes(x)){
      cnt++;
      s += x;
      
    }else{
      cnt = 1;
      s =x 
    }
    if(max < cnt) max = cnt 
  }

  let reversedsStr = str.split('').reverse().join('');
    for(let x of reversedStr){
    if(!s.includes(x)){
      cnt++;
      s += x;
      
    }else{
      cnt = 1;
      s =x 
    }
    if(max < cnt) max = cnt 
  }
  return max
}

마무리 🍯

예외적인 경우의 수를 생각해내는 게 쉽지가 않다.
쩔수없즤,, 계속 여러문제 풀어보는 수 밖에,,, ^-^&***,,,,

profile
꾸준히 성장하기🦋 https://hyodduru.tistory.com/ 로 블로그 옮겼습니다

0개의 댓글