Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Title Description:

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. Note: 0 <= s.length <= 5 * 104 s consists of letters, digits, symbols, and SpacesCopy the code

Ii. Analysis of Ideas:

This problem mainly uses the idea is: sliding window.

  • Define a map data structure storage, use Hashmap to determine whether characters in the string are repeated, where the key value is a character, the value is a character position +1, plus 1 means that the character position does not repeat
  • Let head be the subscript of the left end of the interval, I be the subscript of the right end of the interval,
  • Maintain a left bound head that has no duplicate characters in the sliding window [head, I]. If the next character ch is in the sliding window [head, I], record the i-head. Also update head to the position of CH in the existing sliding window [head, I].

Iii. AC Code:

class Solution { public int lengthOfLongestSubstring(String s) { Map<Character,Integer> map = new HashMap<Character,Integer>(); int head = -1,ans = 0; for(int i = 0; i < s.length(); i++){ char ch = s.charAt(i); if(map.containsKey(ch) && map.get(ch) > head){ ans = Math.max(i - head - 1, ans); head = map.get(ch); } map.put(ch, i); } ans = Math.max(s.length() - head - 1, ans); return ans; }}Copy the code

Iv. Summary:

Writing questions is not easy, if it helps you, click “like” and leave. Remember, (゚▽゚) Blue