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

⭐️ 난이도

Medium

 

---

⭐️ 문제

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

Longest Substring Without Repeating Characters - LeetCode

문자열 s가 주어진다. 

중복이 없는 가장 긴 substring의 길이를 구하라.

 

단, s에는 영문, 숫자, 기호, 공백이 포함되어 있으며, s의 길이의 범위는(0 <= s.length() <= 5 * 10^4)이다.

 

---

⭐️ Follow-up

X

 

---

⭐️ Idea flow

처음에는 영문 소문자만이 포함되는 줄 알았다. 그래서 bool isChecked[26]을 선언하여 중복 여부를 체크하려고 했다.

그런데 문제 조건을 잘 읽어보니 영문만 포함되는 것이 아니라 숫자, 기호, 공백까지 포함이 되기 때문에 bool형 배열을 선언해서 이용하는 것은 무리라고 판단했다.

 

그래서 생각한 것이 또 unordered_map이다. 원하는 값 pair 형식으로 넣을 수 있고, 탐색 속도가 빨라서 활용이 가능하다.

unordered_map<char, int> hashmap을 선언하여 key에는 문자를, value에는 사용 여부를 체크한다.

 

또한 문자가 중복되면 안되기 때문에, 중복된 문자가 들어오면 이를 처리해야 하는데 이를 위해 deque를 사용하기로 했다.

 

마지막으로 substring의 최대 길이를 세기 위해 int cnt도 선언했다.

 

알고리즘은 다음과 같다.

1. string s를 맨 처음(index 0)부터 제일 뒤(index s.length()-1)까지 돌면서 임시 변수 char cur에 저장한다.

2. hashmap에 key 값: cur에 해당하는 value가 있는지 hashmap.count(cur) 이용하여 확인한다. 

 

2-1. 만약 hashmap.count(cur) == 0이라면 중복되지 않는다는 의미이다.

      hashmap[cur] = 1을 통해 사용되었다고 체크를 하고, deque.push_back(cur)을 통해 cur을 넣어준다.

      그리고 cnt++를 하여 substring의 길이를 1 늘려준다.

 

2-2. 만약 hashmap.count(cur) != 0이라면 이미 이전에 사용되었고, 따라서 중복된다는 의미이다.

      먼저 현재까지 구했던 substring의 길이를 확인 후, 더 길다면 갱신을 해준다.

      이후 중복된 문자를 없애기 위해 중복된 문자가 나올 때까지 deque.pop_front()를 실행시킨다.

      pop을 할 때마다 substring의 길이를 1씩 줄임과 동시에 hashmap에서 정보를 삭제한다. (사용 안한 것으로 돌려줌)

      이후 다시 substring을 구하기 위해 현재의 문자를 다시 deque에 넣고, cnt++를 통해 substring의 길이를 1 늘려준다.

 

3. 마지막으로 for문을 모두 돌았으면 substring의 최대 길이 값을 갱신하고 return한다.   

 

 

---

⭐️ Code

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //s contains english, digits, symbols, spaces
        deque<char> dq;
        unordered_map<char, int> hashmap;
        int cnt = 0, result = 0;

        for(int i = 0; i < s.length(); i++){
            char cur = s[i];

            if(hashmap.count(cur) == 0){ // not exists
                hashmap[cur] = 1;
                dq.push_back(cur);
                cnt++;
            }
            else{ // exists
                result = max(cnt, result);
                char tmp = cur;
                while(true){
                    if(dq.front() == tmp){
                        dq.pop_front();
                        cnt--;
                        break;
                    }
                    hashmap.erase(dq.front());
                    dq.pop_front();
                    cnt--;
                }
                dq.push_back(tmp);
                cnt++;
            }
        }
        result = max(result, cnt);
        return result;
    }
};

 

 

---

⭐️ Feedback

 

1. two pointer 알고리즘 사용

   int형 배열과, left & right 포인터를 이용하는 two pointer 알고리즘을 사용하는 방법이 있었다.

   ⓐ int left와 int right 모두 index 0으로 설정

   ⓑ right를 한 칸씩 오른쪽으로 옮기고, 동시에 해당 위치에 있는 문자가 1번 이상 등장했는지 확인한다.

     ⓑ-1. 만일 중복 출현이라면, 중복된 글자가 나올 때까지 left를 오른쪽으로 이동. 동시에 left가 있던 자리의 문자의 빈도수를 1 줄인다.

   ⓒ 현재 두 포인터의 위치를 이용하여 길이를 구하고 (right - left + 1), result값과 비교하여 더 큰 값을 result에 담는다.

 

[전체 코드 보기]

int lengthOfLongestSubstring(string s) {
    //s contains english, digits, symbols, spaces
    int store[256] = {0, }; // store[i]: s[idx]가 몇 번 사용되었는지 저장
    int left = 0, right = 0, result = 0; // left pointer, right pointer, max length

    while(right < s.length()){
        store[s[right]]++;

        while(store[s[left]] > 1){ // 1보다 크다는 의미는 그 문자가 중복됨을 의미
            store[s[left]]--; // 빈도 수를 하나 낮춰주고
            left++; // left pointer를 오른쪽으로 한 칸 이동
        }
        result = max(result, right - left + 1);
        right++; // right pointer를 오른쪽으로 한 칸 이동
    }

    return result;
    // Time complexity : O(2n)
}

//https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1014921/SLIDING-WINDOW-oror-O(n)-oror-Faster-than-90-and-Memory-usage-less-than-100

 

 

2. STL set & two pointer 사용

   위의 방식과 같이 two pointer를 사용했다. 하지만 사용 여부(중복 여부)를 판단하는 방법이 다르다.

   set을 이용했는데, (내가 쓴 코드에서는 unordered_set을 사용) set에 s[i]가 없다면 아직 사용되지 않았다는 뜻이고, 있다면 중복이 되었다는 뜻이다.

   

   만일 set에 s[i]가 없다면

   set에 해당 문자를 insert -> set에 있는 문자의 수가 곧 현재 substring의 길이이므로 필요하다면 갱신 -> right pointer를 오른쪽으로 한 칸 이동

   

   만일 set에 s[i]가 있다면, set에서 해당 문자를 지워주고 left pointer를 한칸 오른쪽으로 옮겨준다.

 

int lengthOfLongestSubstring(string s) {
    //s contains english, digits, symbols, spaces
    unordered_set<char> st;
    int left = 0, right = 0, result = 0;
    int len = s.length();
    
    if(len == 0) return 0; // 만일 s가 비어있는 경우

    while(right < len){
        if(!st.count(s[right])){ // set에 s[right]이 해당하는 문자가 없는 경우 == 아직 사용 x
            st.insert(s[right]);
            result = max(result, (int)st.size());
            right++;
        }
        else{ // 문자가 사용된 경우
            st.erase(s[left]);
            left++;
        }
    }
    return result;
    // https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/577010/C%2B%2B-Solution-using-Set
}

 

 

 

3. two pointer & hashmap 사용

   마지막으로는 hashmap과 two pointer 알고리즘을 같이 사용하는 방법이다.

   unordered_map을 사용한 방법은 나와 유사한데, 다른점은 value에 사용 유무가 아니라 몇 번째 인덱스에서 쓰였는지 저장한 점이다.

   

   if문을 주목할 필요가 있는데, 우리는 hashmap의 value에 몇 번째 인덱스에서 쓰였는지 저장했다.

   그리고 i가 증가하는 것이 right pointer가 오른쪽으로 이동하는 것과 같다.

   따라서 hashmap[s[i]] (즉, s[i]가 쓰인 인덱스)가 이전에 쓰였다면 start의 위치를 중복되는 문자 바로 뒤로 옮겨준다.

   

   그리고 hashmap에 다시 몇 번째 index에서 쓰였는지 갱신한다.

 

int lengthOfLongestSubstring(string s) {
    //s contains english, digits, symbols, spaces

    unordered_map<char, int> hashmap;
    int start = 0, result = 0;

    for(int i = 0; i < s.length(); i++){
        // i번째 문자가 쓰인 적이 있고, 현재 문자의 위치보다 이전의 인덱스에서 쓰였다면
        if(hashmap.count(s[i]) && hashmap[s[i]] >= start){
            start = hashmap[s[i]] + 1; // start의 위치를 옮겨준다 (중복되는 문자 바로 뒤로)
        }

        hashmap[s[i]] = i; // 몇 번째 index에서 쓰였는지 저장
        result = max(result, i - start + 1); // 최대 길이 계산 후, 필요 시 갱신
    }
    return result;
    // https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1177070/C%2B%2B-Sliding-Window-and-Hash-Map-Easy-Solution
}

 

 

처음에 two pointer를 사용하는 것을 보고 와 생각도 못한 방법이다! 라고 생각하며 처음 봤을 때엔 다른 풀이라고 생각된 세 개의 코드를 분석해보았다.

그런데 의외로 세 개의 코드 모두 공통적으로 two pointer를 사용했다는 것을 알 수 있었고, 내 코드 또한 pointer를 사용하진 않았지만 two pointer와 비슷한 풀이라는 것을 알 수 있었다.

 

하지만 내 코드를 뭔가 더 복잡하고 정리가 안된 느낌이 좀 더 강했고, 위 세 개의 풀이는 확실히 깔끔하고 중복된 코드가 없었다.

내 코드도 풀이 방식은 유지하면서 좀 더 간결하고 가독성 좋게 개선할 수 있을 것 같다.

이후에 코드를 좀 더 개선해봐야겠다.