[LeetCode] 3. Longest Substring Without Repeating Characters [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀
문제 👉 <Longest Substring Without Repeating Characters - LeetCode>

1. 문제 (중복 문자 없는 가장 긴 부분 문자열)

중복 문자가 없는 가장 긴 부분 문자열의 길이를 출력하라.

2. 풀이

• 해시와 투 포인터를 이용한 풀이
  • 부분 문자열의 처음과 끝에 포인터를 위치
  • 중복이 없으면 끝을 오른쪽으로 이동
  • 중복이 있을 경우 처음을 오른쪽으로 이동

3. 코드

• 해시와 투 포인터를 이용한 풀이

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ret, start = 0, 0
        used = {}
        for idx, char in enumerate(s):
            if char in used and start <= used[char]:
                start = used[char] + 1 # 한 칸 뒤로
            else:
                ret = max(ret, idx - start + 1)    
            used[char] = idx
        return ret

• 결과 :

Time Submitted	Status	Runtime	Memory	Language
해시와 투포인터	[Accepted]	64 ms	13.8 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋