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

• 문제

Given a string s, find the length of the longest substring without repeating characters.

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

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

문자 s가 주어지면, 반복되는 문자가 없는 가장 긴 하위 문자열의 길이를 찾는 문제입니다.

 

• 문제 해결

반복되는 문자열이 아닌, 반복된 문자가 없는 연속된 문자열을 찾아야 합니다.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        int n = s.size();
        if( n == 0){
            return 0;
        }
        set<char> st;
        int i = 0, j = 0, maxsize = 0;
        while(j < n){
            if(st.count(s[j]) == 0){
                st.insert(s[j]);
                maxsize = max(maxsize, (int)st.size());
                j++;
            }
            else{
                st.erase(s[i]);
                i++;
            }
        }
        return maxsize;
    }
};

 

다른 풀이

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
    if (s.length() == 0) {
		return 0;
	}
	unordered_map<char, int> m;
	int i = 0, j = 0, ans = INT8_MIN;
	while (j < s.length()) {
		m[s[j]]++;
		if (m.size() == j - i + 1) {
			ans = max(ans, j - i + 1);
		}
		else if (m.size() < j - i + 1) {
			while (m.size() < j - i + 1) {
				m[s[i]]--;
				if (m[s[i]] == 0) {
					m.erase(s[i]);
				}
				i++;
			}
		}
		j++;
	}
	return ans;
    }
};