“This is the 11th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

preface

Today this question is a more common type, in the interview from time to time will encounter, the difficulty is not low, force buckle pass rate is only 38.2%, let’s take a look.

Topic describes

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

  • Example 1:

Enter: 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

Enter: 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

Enter: s = “”

Output: 0

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

Subject analysis

In this case, the time complexity of brute force solution is O(n^2), which is not recommended.

In this case, you can define a map set in which the key value is a character and the value value is a character position +1. The value of the map is increased by 1 so that the map starts from the next character position. [left, right] : [left, right] : [left, right] : [left, right] : [left, right] The map and result RES are updated whether or not the left is updated.

Time complexity: Time complexity: O(n)

Code sample

Class Solution {/** * map (k, v) where key = character and value = character position; */ public int lengthOfLongestSubstring(String s) { int n = s.length(), res = 0, left =0; Map<Character, Integer> map = new HashMap<>(); for (int right = 0; right < n; right++) { char alpha = s.charAt(right); if (map.containsKey(alpha)) { left = Math.max(map.get(alpha), left); } res = Math.max(res, right - left + 1); map.put(s.charAt(right), right + 1); } return res; }}Copy the code

In addition, you can also refer to the official website for another way to write:

Class Solution {public int lengthOfLongestSubstring(String s) { Set<Character> ocC = new HashSet<Character>(); int n = s.length(); Int rk = -1, ans = 0; rk = -1; ans = 0; for (int i = 0; i < n; ++i) { if (i ! Occ.remove (s.charat (i-1)); // occ.remove(s.charat (i-1)); } while (rk + 1 < n && ! Occ. contains(s.charat (rk + 1))) {// constantly moving the right pointer occ.add(s.charat (rk + 1)); ++rk; } // the i-rk character is an extremely long non-repeating character substring ans = math.max (ans, rk - I + 1); } return ans; }}Copy the code