Longest Substring W/O Repeating Characters

• Reference
• 말그대로 반복되는 문자가 없는 Substring중 가장 긴 것을 찾는 문제다.

Algorithm

• 브루트포스는 당연히 안된다.. 너무 큰 Time & Space Complexity다.

[a b c d e c a ]

• 위와 같은 문자 리스트를 주었다고 해보자.
• 이 또한 Pointer를 지정함으로써 Substring의 조합을 만들며 길이를 기록해 나갈 수 있다.
• max length, beginIdx, endIdx 3가지 변수가 필요하고, iterator 또는 Idx 변수 2개가 필요할 것이다.
  • p1, p2로 둬보자. p1 : 첫 시작 Idx, p2 : 점점 늘어나는 Idx

[a  b  c  d  e  c  a] => max length 0 begin 0 end 0
p1p2

[a  b  c  d  e  c  a] => max length 2 begin 0 end 1
p1 p2

[a  b  c  d  e  c  a] => max length 3 begin 0 end 2
p1    p2

[a  b  c  d  e  c  a] => max length 4 begin 0 end 3
p1       p2

[a  b  c  d  e  c  a] => max length 5 begin 0 end 4
p1          p2

• 위 처럼 반복되는 문자가 없는지를 체크하며 p2를 이동시키며 max length를 비교하고, 갱신해주면 된다.

[a  b  c  d  e  c  a]
p1             p2

• 반복되는 문자를 만났을 때는 어떻게 해야할까? 먼저, 이전에 봤던 문자는 어떻게 기록할지를 생각해야된다.
  • 어떻게 기록할지는 hash map이 대표적이고, 알파벳이므로 26가지의 array 형태여도 된다.

key	value (p2 Idx)
a	-1 -> 0 -> 6
b	-1 -> 1
c	-1 -> 2
d	-1 -> 3
e	-1 -> 4
f	-1

• 위 처럼 Table로 p1이 바로 이동할 Index를 value에 담고 있으면 된다. -1이 아니면 이 전에 나왔던 문자였을 수 있다.
• 위 Table의 과정은 아래 과정에 의해 업데이트 된다.

[a  b  c  d  e  c  a] => max length 5 begin 0 end 4
         p1    p2     => length 3

[a  b  c  d  e  c  a] => max length 0 begin 0 end 0
         p1        p2 => length 4
         
[a  b  c  d  e  c  a] => max length 0 begin 0 end 0
         p1          p2 => end

• p2가 a를 만나면 Table에서 -1이 아니므로 이미 발생했던 문자인데, p1의 위치의 index가 Table에 기록된 a의 위치보다 크기 때문에 p1이 이동하는 것은 없고, Table에서 key a의 value를 6으로 update만 해준다.

---

• 슬라이딩 윈도우 + 투포인터의 적절한 조합인 문제다.