Longest Substring Without Repeating Characters

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

# Solution

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

# Brute Force

The brute force solution is not shown.

Complexity:

  • time:
    • a nested for loop for the sliding window and to check if unique takes time
  • space:
    • space for the sliding window, where is the size of the Set, which is upper bounded by and

# 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:
    • worst case : all characters are the same and each will be visited by both and
  • space:
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 ( + 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:
  • space:
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