The longest substring without duplicate characters

Offer 48. The longest substring without duplicate characters

Difficulty: Medium

Topic: leetcode-cn.com/problems/zu…

Find the longest substring in the string that does not contain duplicate characters and calculate the length of the oldest string.

Example 1:

Input: "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3.Copy the code

Example 2:

Input: "BBBBB" Output: 1 Explanation: Since the oldest string without duplicate characters is "b", its length is 1.Copy the code

Example 3:

Input: "pwwkew" Output: 3 Explanation: Since the oldest string with no duplicate 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.Copy the code

Hint: s.length <= 40000

Answer key

A string of length N has 1+2+3+… N = (1/2)N(1+N) substring, and the complexity of determining whether the substring is repeated is O(N), so the complexity of violent method is O(N^3), obviously this method AC cannot be used.

First, we can consider using dynamic programming to reduce the time complexity.

Steps:

  • Let dp[j] be the length of the longest non-repeating substring ending in j.

  • Let s[I] be the nearest and equal character to the left of s[j], and let sub[j-1] be the length of dp[j-1]. Note that the characters in sub[j-1] are not repeated. To find a duplicate character s[I] to the left of j, there are two cases:

    • Sub [j-1] sub[j-1] sub[j-1] sub[j-1] sub[j-1] sub[j-1] sub[j-1] sub[j-1] Its length dp[J] = DP [J-1].
    • Sub [j] = sub[j] sub[j] = sub[j]

    If j=4, sub[4] = “CBD”, length dp[4] = 3; if j=4, sub[4] = “CBD”, length dp[4] = 3; When j = 5, s[0] = s[5] and s[0] is outside sub[4], so length dp[5] = dp[4] + 1; When j = 6, s [5] [6] and [5] s = s in sub [5], the dp [6] = j – I = 1.

    Therefore, the formula is:

  • Return the maximum length of the longest non-repeating substring in DP. We can save the space to create the dp array O(N) by updating the maximum value of dp[j] every round of loop.

Method one dynamic programming + hash table

Hash table is used to count the index position of the last occurrence of each character. When traversing s[j], the best index I of the same character can be obtained through the hash table DIC [s[j]].

 / * * *@param {string} s
  * @return {number}* /
 var lengthOfLongestSubstring = function (s) {
   let dic = new Map(a);let res = 0,
     tmp = 0;
   for (let j = 0; j < s.length; j++) {
     let i = dic.has(s[j]) ? dic.get(s[j]) : -1;
     dic.set(s[j], j);
     tmp = tmp < j - i ? tmp + 1 : j - i;
     res = Math.max(res, tmp);
   }
   return res;
 };
Copy the code
  • Time complexity: O(N)
  • Space complexity: O(1)

Method two: dynamic programming + traversal

When s[j] is traversed, the index I = j-1 is initialized, and the first character satisfying s[I] = s[j] is traversed to the left.

 var lengthOfLongestSubstring = function (s) {
   let res = 0, tmp = 0;
   for(let j = 0; j < s.length; j++){
     let i = j - 1;
     while(i >= 0&& s[i] ! == s[j]) i--; tmp = tmp < j - i ? tmp +1 : j - i;
     res = Math.max(res, tmp);
   }
   return res;
 };
Copy the code
  • Time complexity: O(N^2)
  • Space complexity: O(1)

Method three sliding window

Use the dic hash table to calculate the index of the last occurrence of S [J].

  • [I + 1, j]] : I = Max (DIC [s[j]], I)
  • Update the result RES, take the maximum value of the last round RES and the current round sliding window [I +1, j] (i.e., the maximum value of j-i)
 var lengthOfLongestSubstring = function (s) {
   let dic = new Map(a);let res = 0,
     i = -1;
   for (let j = 0; j < s.length; j++) {
     if (dic.has(s[j])) {
       i = Math.max(dic.get(s[j]), i);
     }
     dic.set(s[j], j);
     res = Math.max(res, j - i);
   }
   return res;
 };
Copy the code
  • Time complexity: O(N)
  • Space complexity: O(1)