Leetcode - Algo Challenge Day 6 - 1) Longest Substring Without Repeating Characters

***Sliding window 알고리즘 : 이제껏 들어보지 못한 알고리즘....ㅋㅋㅋ

일정한 범위를 가지고 있는 것을 유지하면서 이것을 이동(sliding)하는 것이다.

*** This can be solved using arrayList, set, and map.

*** 기본적으로 s의 끝까지 돌리고 s에 들어있지 않은 char이면, set에 더하고 max값을 구한다.

   만약에 s가 set에 없으면, start 인덱스를 하나씩 제거하면서 오른쪽으로 이동하게 된다.

  중복되는 char를 만날 때까지 지우게 되므로 중복되지 않는 start 점을 구할 수 있게 된다.

-> sliding window 알고리즘의 원리인 듯

*** 밑의 방법이 조금 색다른 느낌?

*** 처음부터 시작해서 끝까지 확인하는 것은 동일,

그렇지만 만약에 map에 포함되어 있는 것이 있고 현재 단어가 시작하는 인덱스가 map에 포함되어 있는 것의 index 보다 적을 경우에는!!! 반복되면 안되기에 현재 단어가 시작되는 인덱스를 1 증가시킨다. 어차피 그 이후에 똑같은 char가 있기 때문에 substring에는 앞쪽에 나와있던 것이 들어갈 필요가 없기 때문!!!

그 외의 경우에는 제일 긴 길이에 이전의 길이와 현재 인덱스에서 단어가 시작하는 인덱스를 빼준 값 비교

다시 map에는 char를 넣고 이 char의 인덱스 넣기

 

 

*** 제일 빠른 방법인데 array를 사용했으나, 약간 이해가 어렵다...

array를 사용했고 그것 말고는 2번째 방법과 기본적으로 원리는 비슷한 듯 하다.