“This is the 3 days I participated in the November Gwen Challenge. See details of the event: The last Gwen Challenge 2021”.

preface

I have been planning to learn data structures and basic algorithms, but I have seen them in fits and starts. Now I’m determined to stick to it. I’m going to start with LeetCode’s HOT100 and finish 1~2 exercises every day, hoping to develop the habit of continuous learning in this way. Because I am doing iOS development, mainly using Objective-C language, and I am also learning Swift recently, all the questions in this series will be solved using Swift language. What is updated in this paper is the most first-string of 003 without repeating characters, the third question of HOT100 in LeetCode.

The title

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

Example 2:

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

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

Example 4:

Input: s = "output: 0Copy the code

Tip:

0 <= *s.length* <= 5 * 104 s The value consists of letters, digits, symbols, and SpacesCopy the code

Analysis of the

The goal is to find the longest string in a string without repeating characters and return the length of the longest string. The easiest way to think about it is the brute force method (double-loop method), which iterates through the substring of the largest non-repeating character starting with index, but this method has the disadvantage of high complexity, reaching O(n2). The basic idea of this method is as follows:

1. Set two Pointers, left pointer and right pointer to the first element; 2. Move the right pointer until the value of the right pointer is equal to the value of the left pointer to terminate the loop. 3. Move the left pointer one bit to the right and reset the right pointer so that the right pointer equals the left. 4. Repeat steps 2,3 until the left pointer has no value to point to.Copy the code

The increase in complexity of the above method is mainly reflected in the fact that the right pointer is completely recalculated after each change of the left pointer. Through analysis, we found that the sliding window method can effectively reduce the complexity, but we need a dictionary to help us record the last occurrence of each character subscript. The basic idea of this method is as follows:

1. Create an empty dictionary preIndexDic, record the last occurrence of each character, set Pointers startIndex and endIndex, respectively, to indicate the start and end subindexes of the current maximum unique substring, both pointing to 0, set maxLen, Represents the current maximum non-repeating substring length 2 in the string. Check the position preIndex of the last occurrence of endIndex in preIndexDic. If preIndex is after startIndex, startIndex should be changed to 3 after preIndex. MaxLen is the maximum length of the non-repeating substring. The last subscript of the character that corresponds to endIndex is endIndex 4. Move endIndex one bit to the right and repeat 2, 3, 4 steps until there is no value that endIndex can point toCopy the code

Answer key

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        Key :value = ch:index; key:value = ch:index
        var preIndexDic = Dictionary<Character.Int> ()var maxLen = 0  // Record the maximum length
        var startIndex = 0  // Records the start of the current substring
        for (endIndex, ch) in s.enumerated() { 
            // The last occurrence position of the current character, or -1 if not
            let preIndex = preIndexDic[ch] ?? -1 
            // If the last occurrence of the current character was after the start, the current non-repeating substring should start after preIndex
            if preIndex > = startIndex { 
                startIndex = preIndex + 1 
            } 
            preIndexDic[ch] = endIndex  // Refresh the last occurrence of the current character
            let curLen = endIndex - startIndex + 1  // Calculates the maximum length of a character ending with the current character
            maxLen = maxLen > curLen ? maxLen : curLen  // Refresh the maximum substring length
        } 
        return maxLen 
    } 
}
Copy the code