LeetCode-3 Longest Substring Without Repeating Characters 파이썬 풀이

Longest Substring Without Repeating Characters - LeetCode

문제

주어진 문자열에서 중복없이 가장 긴 문자열의 길이를 찾는 문제입니다. 예를 들어 "pwwkew"라는 문자열 안에선 "wke"가 가장 중복없이 긴 문자열이기 때문에 답은 3입니다.

풀이

 

처음 시도했던 방법은 한자리수부터 문자열 길이 만큼의 자리수 까지 점차 늘려가며 가장 중복없이 긴 문자열을 찾는 방법입니다.

1. 중복제거 처리한 문자열과 기존 문자열의 길이를 비교후 같다면 해당 문자열엔 중복이 없다는 뜻이므로 바로 반환

2. max값을 0으로 설정해두고 현재 탐색한 중복없는 문자열의 길이가 max보다 크다면 max 업데이트

3. 자릿수를 증가시켜가며 문자열길이까지 탐색

단순히 처음 시작할때 if문으로 중복이 없을 때를 대비해 두었으니 괜찮을 거라고 생각했지만 역시 time limit Exceeded 되었습니다. 그래서 방법을 바꿔 한자리수부터가 아닌 문자열 길이수부터 한자리수까지 탐색을 시도하였습니다.

 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(set(s)) == len(s):
            return len(s)
        max = 0
        for i in range(0,len(s)):
            j = 0
            while j + i < len(s):
                if len(set(s[j:j+i+1])) > max and len(set(s[j:j+i+1])) == len(s[j:j+i+1]):
                    max = len(set(s[j:j+i+1]))
                j += 1
        return max

그렇지만 마찬가지로 TimeLimit Exceeded되어서 어떻게 하면 시간을 줄일 수 있을 까 고민하다 애초에 중복이 제거된 문자열 길이 수 부터 시작하면 된다는 사실을 깨달았습니다..ㅎ

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(set(s)) == len(s):
            return len(s)
        max = 0
        for i in range(len(s),-1,-1):
            j = 0
            while j + i <= len(s):
                if len(set(s[j:j+i])) > max and len(set(s[j:j+i])) == len(s[j:j+i]):
                    max = len(set(s[j:j+i]))
                j += 1
        return max

중복이 없는 가장 긴 문자열의 길이가 중복을 제거한 문자열의 길이보다 길 수는 없으므로 이방법으로 성공하였습니다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(set(s)) == len(s):
            return len(s)
        max = 0
        maxRepeat = len(set(s))
        for i in range(maxRepeat,-1,-1):
            j = 0
            while j + i <= len(s):
                if len(set(s[j:j+i])) > max and len(set(s[j:j+i])) == len(s[j:j+i]):
                    max = len(set(s[j:j+i]))
                j += 1
        return max