[leetcode 3] Longest Substring Without Repeating Characters

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

 

Example 1:

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

Example 2:

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

Example 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.

Example 4:

Input: s = "" Output: 0

 

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

문제:

겹치는 문자 없는 가장 긴 연속 substring의 길이를 찾기

 

풀이:

- 알파벳만 있는 줄 알고 풀었다가 틀렸다... 문제 조건에서 보면 숫자, 공백, 특수문자도 가능이다. 고로 s[i] - 'a'를 사용하기 보단 map사용이 낫겠다.

- map과 슬라이딩 윈도우를 사용한 문제이다.

 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> m;
        
        int left = 0, right = 0;
        int maxLen = 0;
        while(right < s.length()){
            m[s[right]]++;
            if(m[s[right]] > 1){
                
                while(m[s[right]] > 1){
                    m[s[left++]]--;
                }
            }
            maxLen = max(maxLen, right-left+1);
            right++;
        }
        return maxLen;
    }
};