The oldest string without repeating characters

“This is the third day of my participation in the November Gwen Challenge. See details of the event: The last Gwen Challenge 2021”.

LeetCode 200 simple questions

Topic describes

Given a string s, find the length of the smallest string that does not contain repeating characters.

Example 1:

Input: s = “abcabcbb” Output: 3 Explanation: Since the oldest string without repeating characters is “ABC”, its length is 3.

Example 2:

Input: s = “BBBBB” Output: 1 Explanation: Since the oldest string without repeating characters is “b”, its length is 1.

Example 3:

Input: s = “pwwkew” Output: 3 Explanation: Since the oldest string without repeating characters is “wKE”, its length is 3. Note that your answer must be the length of the substring, “pwke” is a subsequence, not a substring.

Example 4:

Input: s = “output: 0

prompt

• 0 <= s.length <= 5 * 104
• sThe name consists of letters, digits, symbols, and Spaces

Their thinking

Answer: Sliding window + double pointerSet the double pointer,leftwindow-pointingThe left side.rightwindow-pointingThe next element on the right, the window size isright - left. First, setupleft=0 ， right=1, the fixedleftConstantly on the moverightUntil therightThe element that points to already exists in the current window. Then, locate the position of the element in the window and point the head pointer to the next position of that position. orrightIt moves out of the boundarymax_str 与 right - leftReturns the largest substring. Python implementation

class Solution(object) :
    def lengthOfLongestSubstring(self, s) :
        """ :type s: str :rtype: int """
        length = len(s)
        # = 0 or 1, len(s) = the oldest string
        if length < 2:
            return length
        Initialize left and right Pointers
        left, right = 0.1
        The maximum length is set to 1
        max_str = 1
        # Exit condition, right reaches the boundary
        while right < length:
            # When right does not reach the boundary and the element pointing to right does not appear in the substring
            while right < length and s[right] not in s[left: right]:
                # right pointer moves to the right
                right += 1
            max_str = max(max_str, right - left)
            # When right does not reach the boundary
            ifright ! = length:# move the left pointer to the next position on the repeating element
                left += s[left: right].index(s[right]) + 1
        return max_str
Copy the code

Clocking is completed today and the current progress is 7/200.