Python challenge: Leetcode 3. Longest Substring Without Repeating Characters
Tags: python, leetcode
Published: 2022-07-24 17:06:43

## Question
- Given a string `s`, find the length of the **longest substring** without repeating characters.

### Example
- **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.

## My attempt
### Attempt 1 (fail at last two case, exceed time limit)
- algorithm
```
>Find the length of the longest substring without repeating characters.
initialise the length_of_s equals to length of s
initialise the length_list_of_sub_string to the empty string

define a find_and_record_substring program:
	initialise seen_string as an empty string
	initialise seen_dictionary as an empty dictionary
	initialise the length equals to 0
	for each character in s:
	   if the charcter do not found in seen_string:
		   add the character to seen_string
		otherwise:
			initialise the length equals to length of seen_string
			update seen_dictionary with length as key, seen_string as value
			set seen_string to empty string
			add the character to seen_string
	return the maximum of the key of the dictionary

>>find and record each substring without repeating characters in the string s

repeat the find_and_record_substring program for the length of s times:
	add the result of find_and_record_substring program to length_list_of_sub_string
	set s to a s that remove the first character
			
>>return the longest substring without repeating characters
return longest length equals to the maximum of length_list_of_sub_string
```

- code
```python
class Solution:  
    def lengthOfLongestSubstring(self, s: str) -> int:  
        length_of_s = len(s)  
        length_list_of_sub_string = []  
		# program to find each substring without repeating characters in the string
        def find_and_record_substring(str1: str):  
            seen_string = ""  
            seen_dict = {}  
            for char in str1:  
                if char not in seen_string:  
                    seen_string += char  
                # if char found in seen_string
                else:
	                # add the current seen_string to dict first  
                    length_of_seen_string = len(seen_string)  
                    seen_dict.update({length_of_seen_string: seen_string})
                    # clear the seen_string and continue to build seen_string  
                    seen_string = ""  
                    seen_string += char
            # should add the current seen_string to dict
            length_of_seen_string = len(seen_string)  
            seen_dict.update({length_of_seen_string: seen_string})  
            longest_length = max(seen_dict.keys())  
            return longest_length  
        if s == "":  
            return 0  
        while length_of_s != 0:  
            length_list_of_sub_string.append(find_and_record_substring(s))
            # remove the first charcter of s  
            s = s[1::]
            # update the length of s  
            length_of_s = len(s)  
        return max(length_list_of_sub_string)
```

### Attempt 2 (success)
- basically the same way as the above , but add a function to find the upper limit of a substring that is equal to the number of unique character in the string s.
- and when any substring reach the upper limit, the function will not go any forward and return the substring length instead
- code
```python
class Solution:  
    def lengthOfLongestSubstring(self, s: str) -> int:  
        length_of_s = len(s)  
        length_list_of_sub_string = []  
        temp_max = 0  
  
        def longest(str1):  
            set1 = set(str1)  
            return len(set1)  
  
        max_limit = longest(s)  
  
        def find_and_record_substring(str1: str):  
            seen_string = ""  
            seen_dict = {}  
            for char in str1:  
                if char not in seen_string:  
                    seen_string += char  
                else:  
                    length_of_seen_string = len(seen_string)  
                    seen_dict.update({length_of_seen_string: seen_string})  
                    seen_string = ""  
                    seen_string += char  
            length_of_seen_string = len(seen_string)  
            seen_dict.update({length_of_seen_string: seen_string})  
            longest_length = max(seen_dict.keys())  
            return longest_length  
  
        if s == "":  
            return 0  
        while length_of_s != 0 and temp_max < length_of_s and temp_max < max_limit:  
            length_list_of_sub_string.append(find_and_record_substring(s))  
            s = s[1::]  
            length_of_s = len(s)  
            temp_max = max(length_list_of_sub_string)  
        return max(length_list_of_sub_string)
```

## Other solution
- a much faster solution on [Red Crack](https://redquark.org/leetcode/0003-longest-substring-without-repeating-characters/)
```python
def lengthOfLongestSubstring(s: str) -> int:
    # Base condition
    if s == "":
        return 0
    # Starting index of window
    start = 0
    # Ending index of window
    end = 0
    # Maximum length of substring without repeating characters
    maxLength = 0
    # Set to store unique characters
    unique_characters = set()
    # Loop for each character in the string
    while end < len(s):
        if s[end] not in unique_characters:
            unique_characters.add(s[end])
            end += 1
            maxLength = max(maxLength, len(unique_characters))
        else:
            unique_characters.remove(s[start])
            start += 1
    return maxLength
```

## My reflection
- so I learn a new algorithm today called Sliding Window Algorithm.

## Credit
- [leetcode3](https://leetcode.com/problems/longest-substring-without-repeating-characters/)