Leetcode - 3. Longest Substring Without Repeating Characters

문제

문자열이 주어질때, 반복된 문자가 없는 가장 긴 substring의 길이를 구하라.

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

해결 O(N)

sliding window 로 해결. (discussion참고)

• left/right 두개의 포인터를 이동하면서 window의 사이즈를 변경하여 체크.
• 해시테이블에 빈도수를 저장.
• table[s[right]] 이 2 이상 이라면, 1이하로 줄때까지 left를 증가
  • right가 증가하면서 중복된 값을 만났다는뜻.
• update max lenth

1. constraint
 - 0 <= s.length <= 50000
 - s can be all kind of letter
2. Ideas
 - greedy way O(N) -> X
   - using hashtable to check repeated letter exist
 - brute force with Window size -> O(N^2)  
 - sliding window with two pointer (l, r)
   - increase l, while (table[s[r]] > 1)
3. TC

#define TABLE_SIZE 128

int lengthOfLongestSubstring(char * s) {
    int table[TABLE_SIZE] = {0,};
    int ssize = strlen(s);
    int max_len = 0;
    int left = 0, right = 0;
    
    while (right < ssize) {
        table[s[right]]++;
        while (table[s[right]] > 1) {
            table[s[left]]--;
            left++;
        }
        if ((right - left + 1) > max_len)
            max_len = right - left + 1;
        right++;
    }
    return max_len;
}

추가로 배열에서 두개의 인덱스값 a, b 가 주어졌을때 (a<b)라면 a에서 b의 길이는 b - a + 1이다. 당연한거긴 하지만 매번 만날때마다 계산을 하게되서 뇌를 쓰게된다. 그냥 이 패턴을 외우는게 좋겠다. 코딩시 STM을 최소로 사용. 인지적 부하를 최대한 줄이기.
비슷한 내용을 사용한풀이 :
https://velog.io/@soopsaram/Leetcode-5.-Longest-Palindromic-Substring

230817 다시 풀음

해결 아이디어를 떠올리지 못해 또 참고함.

• 해결 아이디어
  • 슬라이딩 윈도우 내부의 빈도수를 해시테이블에 저장.
  • 언제 r을 증가? -> 빈도수가 모두 1이면
  • 언제 l을 증가? -> r위치 문자 빈도수가 2일때

class Solution {
public:
    std::unordered_map<char, int> table;
    int l = 0, r = 0;
    int maxlen = 0;

    int lengthOfLongestSubstring(std::string s) {
        while (r < s.length()) {
            table[s[r]]++;
            while (table[s[r]] > 1) {
                table[s[l]]--;
                l++;
            }
            maxlen = std::max(maxlen, r - l + 1);
            r++;
        }
        return maxlen;
    }
};

또다른 해결 방법

위의 해결방법은 O(2n)인데 아래는 O(n)임. 해시 테이블에 빈도수를 저장하는게 아니라, 해당 문자의 다음인덱스를 저장. r은 하나씩 우측으로 이동하지만, l도 한칸씩 이동할 필요 없음. l은 중복문자가 사라지는 index로 바로 이동하면 됨. l은 r이 직전에 발견되었던 위치+1로 바로 이동하면됨.

class Solution {
public:
    unordered_map<char, int> pos;
    int l = 0, r = 0;
    int maxlen = 0;

    int lengthOfLongestSubstring(std::string s) {
        for (int r = 0; r < s.length(); r++) {
            if (pos.find(s[r]) != pos.end()) // abba
                l = max(l, pos[s[r]] + 1);
            pos[s[r]] = r;
            maxlen = max(maxlen, r - l + 1);
        }
        return maxlen;
    }
};