Title Reference Link

Problem description

Find the longest substring from the string that does not contain repeated characters, and calculate the length of the oldest string.

Algorithm is introduced

1. Dynamically plan DP

The core idea is to decompose the original problem into sub-problems to solve, that is, the idea of divide and conquer. The timing of dynamic programming depends on whether these subproblems are called repeatedly

Dp problems are mainly divided into the following four steps:

  • Partition state, namely partition numerator problem.

  • State representation, that is, how to make the computer understand the subproblem.

  • State transitions, how the parent problem is derived from the child problem.

  • Determine the boundary, determine what the initial state is? Smallest subproblem? What’s the final state.

2. Slide Windows

The double pointer slides constantly to keep it in a reasonable state

solution

Set two Pointers, head and tail. S [tail]-s[head] indicates a non-repeating string

  1. Dynamic programming

  • Direct: dp+ loop to find the right head

  • Optimization: dp + hash

  1. Sliding window – dual pointer

  • Direct: Loop to find the appropriate head

  • Optimization: Hash avoids looping

Code implementation

1. dp + linearTraverse

Assume tail represents the pointer traversed, the latest character currently accessed, and dp[tail] represents the maximum length of a non-repeating substring ending with S [tail]

The state transition equation is as follows:

  • If s[tail] does not appear in s[head]~s[tail-1], dp[tail] = dp[tail] + 1

  • Otherwise, dp[tail] = tail-head

Temp records the length of the current string, and retrieves s[tail] in reverse order to see if it is repeated with an existing string. If not, head -= 1

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: temp = 0 res = 0 for tail in range(len(s)): head = tail - 1 while head >= 0 and s[head] ! = s[tail]: head -= 1 temp = temp + 1 if temp < tail - head else tail - head res = max(temp, res) return resCopy the code
  • Space complexity O(N^2) : the use of a loop to find repeated character time overhead is too large, two layer loop
  • Space complexity O(1) : Several variables use extra space of constant size.

2. dp + hash

Dict is used to update the position of the character S [tail] in S during tail traversal. If the current character already exists, the position is repeated and the value is assigned to head, otherwise head = -1 class Solution: def lengthOfLongestSubstring(self, s: str) -> int: dict = {} res = 0 temp = 0 for tail in range(len(s)): head = dict.get(s[tail], -1) dict[s[tail]] = tail temp = temp + 1 if temp < tail – head else tail – head res = max(temp, res) return res

  • Time complexity O(N) : N is a string length. Dynamic planning requires traversal of the DP list.
  • Space complexity O(1) : The ASCII characters range from 0 to 127. The dict hash table uses a maximum of O(128)=O(1) extra space.

3. Sliding Window

Consider the position of the head and tail Pointers, which make up a sliding window that keeps characters unique

  • ifs[tail]ins[head: tail],head += 1
  • onlyRes and tail - head + 1Update the length
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        head = 0
        res = 0
        for tail in range(len(s)):
            if not s[tail] in s[head: tail]:
                res = max(tail-head+1, res)
            else:
                while s[tail] in s[head: tail]: head += 1
        return res
Copy the code
  • Space complexity O(N) : the use of a loop to find repeated characters time overhead is too large, two layer loop
  • Space complexity O(1) : Several variables use extra space of constant size.

4. Sliding Window + hash

Dict is adopted, and the idea is similar to solution 2

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        head = 0
        res = 0
        dict = {}
        for tail in range(len(s)):
            if s[tail] in dict:
                head = max(dict[s[tail]], head)
            dict[s[tail]] = tail + 1
            res = max(res, tail-head+1)
        return res
Copy the code
  • Time complexity O(N) : N is a string length. Dynamic planning requires traversal of the DP list.
  • Space complexity O(1) : The ASCII characters range from 0 to 127. The dict hash table uses a maximum of O(128)=O(1) extra space.