🟠[Leet code - 3] Longest Substring Without Repeating Characters ★ ✅

Longest Substring Without Repeating Characters - LeetCode

문제

• Input
  문자열 s
• Output
  중복되는 문자가 없는 가장 긴 부분 문자열의 길이
• Constraints
  문자열은 영문, 숫자, 기호, 공백문자 다 포함된다

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

| O(1) : 크게 상관 없음 | O(log n) : 크게  상관 없음 | O(n) :  100'000'000 (1억) | O(n log n) : 1'000'000 (100만) | O(n^2) : 10'000 (1만) |

---

 

$0 \le n \le 50'000$으로, $n \log n$부터 고려해볼 수 있다.

 

 

해결 과정

자연스럽게 윈도우 슬라이딩을 떠올렸고, 핵심 로직은 아래와 같다.

1. 투 포인터 사용해 중복이 없을 때까지 Right를 이동
2. 중복 걸리면 중복 없을 때까지 Left 이동
3. 이걸 Right가 문자열 끝까지 이동할 때까지 반복.

해당 로직은 대략 $2n$이므로 충분히 통과 가능했고, 아래처럼 수도코드를 먼저 작성했다.

 

int ret = INT_MIN;

FOR r from 0 to n
{
    1. s[r] 체크.
    WHILE ( 중복이 있다면 )
    {   
        2. s[l] 체크.
    }

    // 현재 구간의 문자열은 중복이 없음
    // 길이 반환이라 굳이 문자열 저장안해도 돰.
    ret = std::max(ret, r - l + 1);
}

수도코드를 작성하면서 "해당 코드는 중복을 하나만 제거하고 다음으로 넘어가는데, 혹시 다른 중복이 있다면 어떡하지?"라는

생각을 했었는데, 잘 생각해 보니까 그럴 필요는 없었다.

왜냐하면 중복이 처음 생기자마자 중복을 없애는 로직이기 때문에 중복알파벳은 항상 0 ~ 1개로 유지되기 때문이었다.

 

구현

수도 코드와 다른 점은 ret의 초기값이 INT_MIN이 아니라 0으로 바꾸었는데,

문제의 답에 해당하는 최소 값이 0이기 때문이다!

int lengthOfLongestSubstring(string s) 
{
    int ret = 0;
    int check[130] = {0};

    int l = 0;
    for (int r = 0; r < s.size(); ++r)
    {
        char now = s[r];
        ++check[now]; // 체크
        
        // 2개 이상이면 중복상태
        while (2 <= check[now])
        {
            // 현재 l에 속한 빈도수 감소 후 l이동 
            --check[s[l++]];
        }

        ret = std::max(ret, r - l + 1);
    }

    return ret;
}

 

 

되돌아보기

왜 윈도우 슬라이딩이지?

요새 윈도우 슬라이딩을 풀어보는 기간이라 그런지, 자연스럽게 윈도우 슬라이딩을 떠올렸는데, 어떤 부분에 있어서 해당 방법이 고려해 볼 수 있는지 다시 한번 복기했다.

 

이 문제는 부분 문자열을 다루고 있는데, 모든 부분 문자열을 직접 만들어 확인하는 것을 생각하면 오래 걸릴 뿐만 아니라,
코드 또한 복잡하여 풀이하기 어려워, 자연스럽게 최소한의 부분 문자열만 확인하는 방법이 없을까 생각을 해볼 수 있다.

 

슬라이딩 윈도우는 특정 조건을 만족하는 연속된 구간을 보다 편하게 다룰 수 있게 해주는 알고리즘이다.

그렇기 때문에 어떤 연속된 구간의 최대 길이 또는 최소 길이를 구하는 문제에 강점을 보이기도 하는 것 같다.

 

이런 특성을 가졌기 때문에 이러한 문제에서 우선적으로 떠올려볼 수 있지 않을까? 싶다!!

근데 뭔가 지금 정리를 너무 잘한 것 같다.....!!!!!!!

 

아무튼 정리해 보면 문제의 특성이 아래와 같은 때 한 번 고려해 보자.

• 연속된 구간을 다루는가?
• 해당 구간이 만족해야 하는 조건이 있는가?
• 조건이 깨졌을 때 Left를 움직여 복구할 수 있는가?