This is the 18th day of my participation in the Gwen Challenge.More article challenges

For a better tomorrow, keep brushing LeetCode!

The title

Given a string, 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

Solution one – sliding window

Their thinking

Each loop stores each character in the hash table. When the same character is found in the hash table, the loop ends, and the length of the hash table is compared with the length of the current oldest string (0 at the beginning), the larger one is taken, and the hash table is reset at the same time for the next loop.

The outer loop starts at 0, and the inner loop starts at the index +1 of the outer loop.

code

func lengthOfLongestSubstring(s string) int {
    m := make(map[byte]bool)
    l := 0
    for i, _ := range s {
        m[s[i]] = true
        for j := i+1; j < len(s); j++ {
            if _, found := m[s[j]]; found {
                if l < len(m) {
                    l = len(m)
                }
                m = make(map[byte]bool)
                break
            }
            m[s[j]] = true}}if l < len(m) {
        l = len(m)
    }
    return l
}
Copy the code

The execution result

Execution time: 364 ms beat 5.03% of users memory consumption in all Go commits: 7 MB beat 5.29% of users in all Go commitsCopy the code

Complexity analysis

  • Time complexity: O(N), whereNIs the length of the string. The subscripti 和 jEach iterates through the entire string once.
  • Space complexity: O(∣ Σ ∣), whichΣRepresents a character set (that is, the characters that can appear in a string),∣ Σ ∣Represents the size of the character set. In this case, the character set is not specified, so we can default to all ASCII characters within [0, 128], i.e∣ Σ ∣= 128. We need to use the hash set to store the characters that appear, and the characters are at most∣ Σ ∣, so the space complexity is O(∣ Σ ∣).

Topic link

3. The oldest string without repeating characters