0003. Longest Substring without Repeating Characters

0003. Longest Substring without Repeating Characters#

Problem#

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

Examples#

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

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.

Constraints:#

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Analysis#

  • Method 1:

    • unique characters can be represented as set. We need maintain a set with maximum length meeting the requirements

    • algorithm:

      • initialize a string to store the resulted string, and a variable that records its length

      • use two pointers i, j to iterate over the whole string starting from the beginning of the string,

        • if \(A[j] \ne A[i]\), then move pointer j right by 1, and record current unique substring in a set, increase the maximum length by 1

        • if \(A[j] = A[i]\), then move the pointer i to j and j to j+1, and start the loop again

Solution#

# Solution 1: sliding window with two pointers -> $O(n)$ time + O(n) space
def solution(s):
    n = len(s)

    i = 0
    j = i + 1
    l = 1
    l_max = 1
    r = s[i]
    res = r
    while i<n-1 and j<n:
        if s[j] not in r:
            r += s[j]
            j += 1
            l += 1
            res = r
        else:
            if l > l_max:
                res = r 
            i = j
            j += 1
            l = 1
            r = s[i]

    return res

s = "abcabcbb"
print(solution(s))

s = 'bbbb'
print(solution(s))

s = "pwwkew"
print(solution(s))

abc
b
wke

# Solution 2: another two-pointer sliding window implementation
def solution(s):
    window_map = {}

    left, right = 0, 0
    max_length = 0

    while right < len(s):
        c = s[right]
        window_map[c] = window_map[c] + 1 if c in window_map else 1
        # update
        right += 1 

        while window_map[c] > 1:
            # update length
            length = len(window_map)
            max_length = max(max_length, length)

            # shrink window as duplicates are found
            d = s[left]
            window_map[d] -= 1
            if window_map[d] == 0: window_map.pop(d)
            left += 1
    
    return max_length

# test
s = "abcabcbb"
print(solution(s))

s = 'bbbb'
print(solution(s))

s = "pwwkew"
print(solution(s))

3
1
3
Contents