Day030 - 3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray (A subarray is a contiguous non-empty sequence of elements within an array.) whose sum is greater than or equal to target.

If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

내 풀이

from collections import defaultdict

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0: return 0
        """
        마찬가지로 sliding-window를 사용해서
        l, r = 0_index부터 시작해서 r 하나씩 올리면서 중복 나올때까지 진행
        중복 나오면 중복 나온 시점으로 다시 l, r 포인터 옮겨서 다시 체크
        """

        "abcde c"

        l, r = 0, 1

        check_dict = defaultdict(bool)
        check_dict[s[0]] = True

        longest_sub = 1
        current_sub = 1

        while r < len(s):
            if check_dict[s[r]]: # 나왔던적이 있으면 l 옮기며 해당 글자 나올때까지 진행
                longest_sub = max(longest_sub, current_sub)
                while s[l] != s[r]:
                    check_dict[s[l]] = False
                    l += 1
                    current_sub -= 1
                    
                l += 1
                current_sub -= 1
                longest_sub = max(longest_sub, current_sub)

            else: # 나왔던적이 없으면
                check_dict[s[r]] = True

            r += 1
            current_sub += 1
                
        return max(longest_sub, current_sub)

# Time Complexity : \(O(N)\)