[Leetcode]3. Longest Substring Without Repeating Characters

📄 Description

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.

🔨 My Solution

• (case1) Don't need to check substrings
  ❕ If the string is empty or only one character, the longest substring is the string itself.
• (case2) Need to check substrings
  ❕ There is two ways to repeate the charater
  1. repeat successively
  • then, the substring will newly start with the current character
  2. repeat not succesively
  • then, the substring will be without the substring which ends with the first character that repeats.

💻 My Submission

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        if not s or len(s)==1:
            return len(s)

        substring=""
        longest=""

        for i in range(0,len(s)):
            if s[i] not in substring:
                substring+=s[i]
                if len(substring)>len(longest):
                    longest=substring
            elif substring[-1]==s[i]:
                substring=s[i]
            else:
                substring=substring[substring.index(s[i])+1:]+s[i]

        return len(longest)

🔎 Complexity

Time Complexity: O(n)
The worst case is going all through each character of the string s.
Space Complexity: O(1)
In the worst case we would have to store all n characters of the string s in hashmap, but this is a constant value which at max can go up to O(62) as explained in solution 1.

💊 How to improve my solution?

📌 Sliding Window Method

I realized that my solution is similar to the "Sliding Window" Method, and there is a lot of parts to be improved.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = start = 0
        for i in range(len(s)):
            if s[i] not in s[start:i]:
                max_len = max(max_len, i+1-start)
            else:
                start+=(1+s[start:i].index(s[i]))
        return(max(max_len, len(s)-start))

This solutions is a better approch because
1. It covers the both ways to repeate the charater which I handled them differently.
2. It doesn't use memory for saving the substring and the longest substring.

References
https://leetcode.com/problems/longest-substring-without-repeating-characters/
https://www.code-recipe.com/post/longest-substring-without-repeating-characters
https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1843466/Python-sliding-window-faster-than-90