[C++] LeetCode : Longest Substring Without Repeating Characters

Question

문자열 s가 주어졌을 때, 한 문자가 두 번 이상 등장하지 않는  가장 긴 부분 문자열을 찾아 그 길이를 return 하라. 

 

제약사항

• s의 길이는 0 이상 5 * 10^4 이하이다.
• s는 영문, 숫자 및 심벌과 공백으로 이루어져 있다. 

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

  모든 문자열의 문자들을 최소 한 번식은 봐야 하기 때문에 O(s)이다.

 

고려사항

1. 제약사 항의 영문 이외의 문자가 들어갈 경우

---

Solution1 - Brute Force

가장 긴 문자열부터 문자열의 길이를 하나씩 줄여가면서, 중복된 문자가 있는지 판단한다

substr의 길이가 s일 때 1번(s)
substr의 길이가 s-1 일때 2번(s-1)
substr의 길이가 s-2 일때 3번
..
substr의 길이가 2 일 때 (s-1)번
substr의 길이가 1 일때 s번 -> answer is 1
즉, 총 s + 2(s-1) + 3(s-2)+ 4(s-3)... s(s-s+1) + s+1(s-s)으로
시간 복잡도는 O(n^3)이다

---

Solution2 - Two Pointer

  양끝을 기준으로 판단하는 방식 길이를 하나씩 줄여가며 substr의 모든 구성 char가 개수 1을 만족하는지 판단.
substr의 길이가 s일 때 s만큼 탐색
substr의 길이가 s-1일 때 s-1만큼 탐색
...

substr의 길이가 1일 때 1만큼 탐색으로
시간 복잡도는 s(s+1)/2 = O(s^2)이다

---

Solution3 - Sliding Window

two pointer를 양끝이 아닌 시작점에 두고 조금씩 늘려가면서 찾는 방식이다. hash를 써서 해당 문자 등장 개수가 1개 이상일 때 substring 길이를 줄였다 늘렸다를 반복하여 가장 긴 문자열을 찾는 방식이다

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> char_counter;
        
        int start = 0, end = 0, longest = 0;
        while (end < s.size()) {
            char_counter[s[end]]++;
            
            while(char_counter[s[end]] > 1){
                char_counter[s[start++]]--;
            }
            
            longest = max(longest, end - start + 1);
            end++;
        }

        return longest;
    }
};

• Time complexity : O(n) // 최악의 경우 start와 end가 계속 반복해서 바뀌는 경우로 이럴 경우 2번 돌아야 하기 때문에 O(2n)으로, Time Complexity는 O(n). 
• Space Complexity : O(s) // 모든 문자가 hash에 들어갈 경우 필요하다.

출처 : https://leetcode.com/problems/longest-substring-without-repeating-characters/solution/

Longest Substring Without Repeating Characters - LeetCode

* 본 포스트 관련된 토의, 지적 및 조언은 모두 환영합니다