3. Longest Substring Without Repeating Characters — LeetCode(Python)

I got you!

Problem:

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

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:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

Solution:

1. “Last Viewed At” Method —

d = {}
max_len = 0
        
l = 0
for r in range(len(s)):
    if s[r] in d and l <= d[s[r]]:
        l = d[s[r]] + 1
    else: 
        max_len = max(max_len, r - l + 1)
    d[s[r]] = r
            
return max_len

Explanation —

We use a two-pointer sliding window technique here.

We create a dictionary to store the characters in a given window. The keys are the characters themselves, and the values are the last index at which the character was seen.

As we iterate through the string, we check if the new character in the window is already in the dictionary. If so, we slide the left end of the window to the point right next to this previous character.

There is a caveat here. What is the new element already exists in the array at a point before the window, i.e. before l?!

To make sure, we don’t slide the window back in reverse, we put the following check:

if l <= d[s[r]]:

Dry run through this example string — “tmmzuxt”, to understand this better.

After doing this, we update the max_len if required, and we keep sliding the window.

Finally, we return the max_len.

Time and Space Complexity —

Since iterating through an array is a linear time operation, we can say that our algorithm requires linear time to run.

Also, we require constant extra space, since our dictionary is only a mapping of valid Python characters to the indices they were encountered at. And we know,

s consists of English letters, digits, symbols and spaces.

Thus, if n is the length of the string s,

Time Complexity: O(n)

Space Complexity: O(1) [amortized]

2. Using A Set —

charSet = set()
l = 0
res = 0
        
for r in range(len(s)):
    while s[r] in charSet:
        charSet.remove(s[l])
        l += 1
    charSet.add(s[r])
    res = max(res, r - l + 1)
        
return res

Explanation —

We are using a sliding window technique here as well.

While adding new characters in our set, we are popping elements from the set until there are no repeating characters in the window.

After that we shrink the window from the left.

We then add this latest character in the set.

Then, the maximum length of the window is updated and stored in res.

Finally, res is returned.

Time and Space Complexity —

Since we are visiting all characters in the string once, this is a linear time operation.

Since every character in the string could be unique, we need linear space.

Thus, if n is the length of the string s,

Time Complexity: O(n)

Space Complexity: O(n)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏