This is the fifth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

The longest substring without repeating characters

Pointer to Offer 48. Longest substring without repeating characters

Difficulty: Medium

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

Find the longest substring from the string that does not contain repeated 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 repeating characters is "b", its length is 1.Copy the code

Example 3:

Input: "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.Copy the code

Tip: S.length <= 40000

Answer key

A string of length N has 1+2+3+… + N = 1/2 N ∗ ∗ (1 + N) 1 + 2 + 3 +… +N = 1/2*N*(1+N)1+2+3+… +N=1/2∗N∗(1+N) substring, while the complexity of determining whether the substring is repeated is O(NNN), so the complexity of violent method is O(N3N^3N3), which obviously cannot be used by AC.

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

Steps:

  • Let dp[j] be the length of the longest unrepeatable substring ending in j.

  • Set the closest and equal character to the left of character s[j] as s[I], and the substring sub[j-1] ending with character s[j-1] as dp[j-1]. Note that the characters in sub[j-1] are not repeated. To find a repeated character s[I] to the left of j, there are two cases:

    • Index I in sub string [1] interval, which is sub [1] left more on the left side of the border, the dp] [j – 1 < j – I, as a result of sub characters in [1] is not repeated, and the longest, so the substring sub [1] in the back to s [j]. Its length dp[j] = DP [J-1].
    • If sub[j] is in the interval of sub[j-1], then dp[j-1] ≥ j-i, then the left boundary of sub[j] can only be I, and its length dp[j] = j-i.

    For example, [abcdbaa], the index starts at 0, when j=4, sub[4] = “CBD”, length dp[4] = 3; When j = 5, s[0] = s[5] and s[0] is outside sub[4], so the 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:


    d p ∣ j ∣ = { d p [ j – 1 ] + 1 . d p [ j – 1 ] < j – i j – i . d p [ j – 1 ] p j – i Dp | | = j \ begin {cases} dp] [j – 1 + 1, dp] [j – 1 < j – I \ \ j – I, quad, quad, quad, dp] [j – 1 p j – I \ end {cases}

  • Returns the length of the longest non-repeating substring in dp. TMP is used to store crude dp[j], and the maximum value can be updated in each cycle, so as to save space for creating dp array O(NNN).

Method 1 dynamic programming + hash table

The 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(NNN)
  • Space complexity: O(111)

Method 2 dynamic programming + traversal

If s[I] = s[j], I = j-1; if s[I] = s[j], I = j-1;

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(N2N^2N2)
  • Space complexity: O(111)

Method three sliding window

Mysql > alter table dic (s[j]);

  • I = Max (dic[s[j]], I) I = Max (dic[s[j]], I) I = Max (dic[s[j]], I) I = Max (dic[s[j]], I)

  • Update the result res, take the maximum value of the upper round RES and the epicycle 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(NNN)
  • Space complexity: O(111)

Practice every day! The front end is a new one. I hope I can get a thumbs up