This is the 13th day of my participation in the August More Text Challenge.More challenges in August

The oldest string without repeating characters

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

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

A substring is a contiguous segment of a string.

The violent solution method is used to judge each substring once. If repeated characters appear, the substring is discarded; if not, the length is counted and the longest substring is found. The time complexity of this solution is O(n^2), which obviously times out.

To improve the brute force solution, start with the string itself and reduce the length until you find a non-repeating substring, returning that length directly. It’s barely passable, but the worst complexity is O(n^2), which is not as expected.

Because it is continuous, we can try to use a sliding window to judge.

First, let’s define a sliding window:

1. The sliding window consists of two Pointers on the left and right, both of which start at 0.

2. When the window moves, leave the left pointer unchanged and only move the right pointer to expand the substring.

3. If there are duplicate characters in the substring, we use map to store the position where the characters appear.

4. Whether the next character of the right pointer already exists in the map, if so, the left window moves right to the next bit where the character appears (because there must be duplication between the left pointer and this bit); Otherwise, repeat Step 2.

5. Every time the window is refreshed, the window length should be calculated. If it is larger than the maximum window length of the original mark, it will be updated.

In addition, pay attention to some boundary conditions, such as string length cannot be 0, otherwise the array will be out of bounds;

In this way, the result can be obtained in a single traversal with time order (n).

The code implementation is as follows:

func lengthOfLongestSubstring(s string) int {
   if len(s) == 0 {
      return 0
   }
   l, r, Max := 0.0.0
   m := map[byte]int{}
   for ; r < len(s); r++{
      if_,ok := m[s[r]]; ! ok { m[s[r]] = r }else {
         if m[s[r]] + 1 >= l {
            l = m[s[r]] + 1
         }
         m[s[r]] = r
      }
      if r - l + 1 > Max {
         Max = r - l + 1}}return Max
}
Copy the code

Submission Results: