[LeetCode] 3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-interview-150 

Longest Substring Without Repeating Characters - LeetCode

문제 유형 : 문자열 처리 / 슬라이딩 윈도우

문제 난이도 : Medium

 

문제

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

문자열 s가 주어집니다. 반복되는 문자 없이 가장 긴 부분 문자열의 길이를 찾으시오.

 

풀이

가장 긴 부분 문자열이 가지는 문자 집합을 만든다.

left 포인터를 키우면서 중복되는 문자를 없앤다. 중복 문자가 없는 범위에서 길이를 구해서 이전 최대 길이와 비교한다.

문자열을 다 돌고 최대 길이를 반환한다.

 

코드

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        const int n = s.size();
        int left = 0;
        int maxLen = 0;
        unordered_set<char> charSet;

        for (int right = 0; right < n; right++) {
            while (charSet.count(s[right])) {
                charSet.erase(s[left]);
                left++;
            }
            charSet.insert(s[right]);
            maxLen = max(maxLen, right - left + 1);
        }

        return maxLen;
    }
};

 

Python3

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        maxLen = 0
        left = 0
        charSet = set()

        for right in range(n):
            while s[right] in charSet:
                charSet.remove(s[left])
                left += 1
            charSet.add(s[right])
            maxLen = max(maxLen, right - left + 1)

        return maxLen

 

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int left = 0;
        int maxLen = 0;
        HashSet<Character> charSet = new HashSet<>();

        for(int right = 0; right < n; right++) {
            while(charSet.contains(s.charAt(right))) {
                charSet.remove(s.charAt(left));
                left++;
            }
            charSet.add(s.charAt(right));
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
        
    }
}