[LeetCode, 리트코드] Longest Substring Without Repeating Characters

1. Problem

주어진 문자열에 대해 가장 긴 부분문자열을 찾아라. 단, 같은 문자가 반복되선 안 된다.

Example 1:

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

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

2. Solution

 

윈도우를 나타내기 위한 i, j 변수를 준비한다. 윈도우의 오른쪽을 나타내는 j를 가지고 배열을 순회한다. 만약 문자가 현재 발견되지 않았을 시에는 해쉬에 저장한다. 만약 중복된 문자가 나타났을 경우에는 2가지 방법으로 이 경우를 처리하면 된다.

1. 만약 이전 중복된 문자의 인덱스가 윈도우의 왼쪽을 나타내는 i보다 작을 경우 이를 무시한다. 왜냐하면 이 문자는 window에 포함되지 않았기 때문

2. i보다 클 경우에는 i를 바로 오른쪽에 위치한 인덱스로 업데이트 한다 (hash[s_char + 1]). 이러는 이유는 중복된 문자가 window에 포함되는 것을 막기 위해서다. 또한 현재 문자를 hash에 업데이트 한다.

3. What I solved

class Solution {
public:
    unordered_map hash;
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0)
            return 0;
        
        int i = 0;
        int j = 0;
        int ret = 0;
        int temp = 0;
        
        while(j < s.size()){
            char s_char = s[j];
            if(hash.find(s_char) == hash.end() || hash[s_char] < i){
                hash[s_char] = j;
                temp++;
            }
            else {
                i = hash[s_char] + 1;
                temp = j - i + 1;
                hash[s_char] = j;
            }
            ret = max(ret, temp);
            j++;
        }
        return ret;
    }
};