[leetcode] 3. Longest Substring Without Repeating Characters

 

3. Longest Substring Without Repeating Characters

 

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

 

방법1

NO_OF_CHARS = 256 
class Solution:
    def lengthOfLongestSubstring(self,s):
        """
        :type s: str
        :rtype: int
        """
        # 마지막 인덱스 array를 -1로 초기화 
        lastIndex = [-1] * NO_OF_CHARS
        n = len(s)
        res = 0 
        i = 0 
        
        for j in range(0,n):
            # str[j]의 마지막 인덱스를 찾아서 +1을 하고  
            # 현재 i 값과 last의 최댓값으로 
            # i를 업데이트, 
            i = max(i, lastIndex[ord(s[j])]+1)
            
            # 더 큰 결과로 결과값 업데이트 
            res = max(res, j-i+1)
            
            # 마지막 인덱스를 j로 업데이트 
            lastIndex[ord(s[j])] = j 
    
        return res

방법2

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        substring = “”
        max_length = 0
        for c in s:
            found = False
            for (i, one_character) in enumerate(substring):
                if c==one_character:
                    found = True
                    max_length = max(max_length, len(substring))
                    substring = substring[i+1:] + c
                    break
            if not found:
                substring = substring + c
        if len(substring) != 0:
            max_length = max(max_length, len(substring))
        return max_length
#1 아무것도 없는 substring 만들기 “”
#2 가장 긴 substring 길이 저장하기 3
#3 한글자씩 가져오기 c = “w” -> 글자가 없으면 현재 substring 에 있는 것이 가장 긴지 확인
#4 가져온 글자가 subtring 에 있는지 확인 “w”
#5 있으면 -> 현재 substring 에 있는 것이 가장 긴지 확인 -> 현재 substring 에서 발견한 글자 index + 1부터 자르고, + c
#6 없으면 -> 현재 substring 에 c를 추가
#3-6 부터 반복

 

 

출처 

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

Longest Substring Without Repeating Characters - LeetCode