LeetCode No.3 Longest Substring Without Repeating Characters

This is a test for post writing in English, as well as my writing skill practice. The test is to check the Google search data in Google Search Console for English posts.

I chose LeetCode problems for the test. Since I am not an expert in algorithm, I just show my solutions with explanations for the problems and do not pursue better performance. The series of the posts will be updated due to my personal interest if the problem attracts me, and more importantly, I am able to solve the problems 😛.

P.S. I use Python 3 in LeetCode.

Problem Description

Check the original URL:

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

Example 1:

Input: s = "abcabcbb"
Output: 3
xplanation: 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 Idea

The main idea is to read the items in the string one by one, meanwhile construct a new substring to store the read items. The length of the new substring should be counted as our goal is to find the maximum length.

Here comes to the duplicated items:

In the loop of item reading, if we find the newest item is duplicated in previous substring, we should update the substring to avoid duplication with trim the early used item. For example, if the previous substring is ***x*** (* is not x) and the newest item is x, then the previous 4 items should be trimmed and substring should be update to ***x. So the method is to find the index of the duplicated item and complete the trim.

After all the items are read, return the maximum length of substrings.

My Code

Here is my submitted code:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max = 0
        a = []
        count = 0
        for item in s:
            if item not in a:
                a.append(item)
                count = count + 1
                if count > max:
                    max = count
            else:
                index = a.index(item)
                a = a[index + 1::]
                a.append(item)
                count = len(a)
        return max