Longest Substring Without Repeating Characters

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

# Solution

Let nn be size of the string, mm the size of the charset/alphabet.

# Brute Force

The brute force solution is not shown.

Complexity:

  • time: O(n3)O(n^3)
    • a nested for loop for the sliding window and to check if unique takes O(n)O(n) time
  • space: O(min(m,n))O(\min(m,n))
    • O(k)O(k) space for the sliding window, where kk is the size of the Set, which is upper bounded by nn and mm

# Sliding Window Using HashSet

The idea is to use a sliding window to locate a substring, and a HashSet st to see if the new char is already seen previously.

Sliding window logic: i is the left boundary and j the right boundary. Increase j by 1 if s[j] has not occurred in the current subarray. Increase i if s[j] has occurred.

Invariant: i<=j

Complexity:

  • time: O(n)O(n)
    • worst case O(2n)O(2n): all characters are the same and each will be visited by both ii and jj
  • space: O(min(m,n))O(\min(m,n))
def lengthOfLongestSubstring(self, s: str) -> int:
    if not s: return 0
    n = len(s)
    st = set()
    i = j = 0
    res = 1
    while i<n and j<n:
        if s[j] not in st:
            st.add(s[j])
            j += 1
            res = max(res, j-i)
        else:
            st.remove(s[i])
            i += 1
    return res

# Sliding Window Using HashMap

If having seen the new char in existing window, could update the left boundary to d[val]+1 (11 + index of last duplicate in the window).

Several optimizations:

  1. start and idx rather than i and j to refer to left and right boundaries of window
  2. enumerate idx and val
  3. dct to store the mapping from val to idx

Complexity:

  • time: O(n)O(n)
  • space: O(min(m,n))O(\min(m,n))
def lengthOfLongestSubstring(self, s: str) -> int:
    res = 0
    start = 0
    dct = {}
    for idx, val in enumerate(s):
        if s[idx] in dct:
            start = max(start, dct[val]+1)
        res = max(res, idx-start+1)
        dct[val] = idx
    return res
Last Updated: 7/19/2020, 3:45:14 PM