[Leetcode] 3. Longest Substring Without Repeating Characters

🖥️ 시작하며

from typing import List


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = 0

        for i in range(len(s)):
            # 길이를 저장할 임시 변수
            tmpres = 0
            
            # substring에 문자가 더 들어가는지 확인
            for j in range(i, len(s)):
                if s[j] in s[i:j]:
                    break
                tmpres += 1
            res = max(res, tmpres)

        return res


s = Solution()
print(s.lengthOfLongestSubstring("pwwkew"))

from typing import List


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = 0
        visit = set()
        left = 0  # 왼쪽 idx

        # 오른쪽 idx부터 시작
        for right in range(len(s)):
            # visit에 있다면, visit에서 삭제하고 left 인덱스 증가
            # left와 right를 이용해 전체 길이 구함
            while s[right] in visit:
                visit.remove(s[left])
                left += 1
            # visit에 문자 추가
            visit.add(s[right])
            res = max(res, right - left + 1)
        return res


s = Solution()
print(s.lengthOfLongestSubstring("pwwkew"))

• 문자 p를 처리할 때 visit = {'p'}, res = 1.

• 문자 w를 처리할 때 visit = {'p', 'w'}, res = 2.

• 또 다른 w를 만나면 visit에서 p를 제거하고 l을 이동, visit = {'w'}, res = 2.

• 문자 k를 처리할 때 visit = {'w', 'k'}, res = 2.

• 문자 e를 처리할 때 visit = {'w', 'k', 'e'}, res = 3.

• 마지막으로 w를 처리할 때 visit에서 w 이전 문자를 제거하고, 최종적으로 visit = {'k', 'e', 'w'}, res = 3.

⚙️ Python

from typing import List


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = 0
        visit = set()
        left = 0  # 왼쪽 idx

        # 오른쪽 idx부터 시작
        for right in range(len(s)):
            # visit에 있다면, visit에서 삭제하고 left 인덱스 증가
            # left와 right를 이용해 전체 길이 구함
            while s[right] in visit:
                visit.remove(s[left])
                left += 1
            # visit에 문자 추가
            visit.add(s[right])
            res = max(res, right - left + 1)
        return res


s = Solution()
print(s.lengthOfLongestSubstring("pwwkew"))

⚙️ C++

#include <iostream>
#include <set>
#include <string>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        set<char> visit;
        int left = 0;

        for (int right = 0; right < s.length(); ++right) {
            while (visit.find(s[right]) != visit.end()) {
                visit.erase(s[left]);
                left++;
            }
            visit.insert(s[right]);
            res = max(res, right - left + 1);
        }

        return res;
    }
};

int main() {
    Solution solution;
    string test = "pwwkew";
    cout
        << solution.lengthOfLongestSubstring(test) << endl;
    return 0;
}

📌 소감

🔍 부록

🔍 참고문헌