[LeetCode] 3. Longest Substring Without Repeating Characters (C++)

문제

문자열 s 중에서 반복되지 않는 가장 긴 문자열 개수 찾기

생각할 것

먼저 문제의 조건을 이해해보자.

 

예제 1.

주어진 문자열이 abcabcbb라고 했을 때

길이가 1일 때를 제외하고 ab, bc, ca, bca, cab, bc, cb와 같은 문자열이 반복되지 않는 문자열에 해당한다.

abca가 불가능한 이유는 abc 이후에 다시 a가 오면 다시 반복이 시작되기 때문이다.

 

예제 2.

bbbbb일 경우 당연히 b가 답이다.

b다음 다시 b가 오면 b가 두번 반복 되기 때문이다.

 

예제 3.

pwwkew이면 길이가 1일 때를 제외하고 pw, wk, wke, ke, ew같은 문자열이 가능하다.

따라서 가장 긴 문자열은 3이다.

---

이를 해결하기 위해서는 해시맵과 투포인터를 사용할 수 있다.

💡 two pointers 알고리즘

• 두개의 포인터를 이용하여 양 끝의 원소만 갱신하는 방법
• 구간의 넓이가 조건에 따라 변경될 수 있다.
• O(N) 

💡 sliding window 알고리즘

• 양 끝의 원소만 갱신하는 방법이라는 점은 동일
• 항상 구간의 넒이가 고정되어 있다.
• O(N)

최대 길이가 유동적으로 변할 수 있다고 생각하여 위의 두가지 방법 중 투포인터 알고리즘을 선택했다.

결과 코드

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> m; // 해시맵은 투포인터 사이에 있는 문자열 인덱스를 나타냄
        int start = -1; // 반복 문자열의 시작 인덱스
        int maxLen = 0;
        for(int i=0; i<s.length(); i++){
            if(m.find(s[i]) != m.end()){  // 새로운 문자열이 맵에 존재하면
                **if(m[s[i]] > start)**{
                    start = m[s[i]]; // start를 해당 위치로 변경
                }
            } 
            m[s[i]] = i; // 인덱스 값 넣기
            maxLen = max(maxLen, i - start); // 최대 길이 갱신
        }
        return maxLen;
    }
};

반례

if(m[s[i]] > start) 해당 조건이 없으면 abba의 조건을 통과하지 못한다.

해당 조건이 없는 경우 m[’a’]의 값이 0이고 start가 1일 때,

다시 a를 만나면 start가 0이 되기 때문에 현재 start 위치보다 큰 경우에만 갱신해야 한다.

추가 사항

map의 find에 대한 시간 복잡도 : tree이므로 O(log(N))

unordered_map의 find에 대한 시간복잡도 : hash table이므로 O(1)