[LeetCode] 3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

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

주어진 문자열 s에서 문자열이 반복되지 않는 가장 긴 길이를 찾는 문제이다.

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.

"pwwkew"가 주어질 경우, pwke는 substring이 아니기 때문에 답이 될 수 없다. 즉, 연속된 문자열이어야 한다는 것이다. 이를 참고하여 문제를 풀어보자.

문자열을 순회하며 문자가 answer 배열에 없으면 그대로 추가하고, 있으면 해당 문자의 앞까지 잘라서 버리고 난 후 추가하였다. 가장 긴 길이는 answer 배열에 있을 때마다 업데이트 해주었고, 순회가 끝난 후 한 번 업데이트 해주었다.

처음 풀었을 땐, 문자를 모두 아스키코드로 바꾼 후 진행하여 72ms가 나왔다. 이후 생각해보니 굳이..? 이길래 없애고 제출하니 60ms가 나왔다. 오예.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ret = 0
        answer = []
        for ch in s:
            if ch not in answer:
                answer.append(ch)
            else:
                ret = max(ret, len(answer))
                answer = answer[answer.index(ch)+1:]
                answer.append(ch)

        ret = max(ret, len(answer))
        return ret