LeetCode-3. The longest string without repeating characters uses an integer array +ASCII code to implement the sliding window

Look at the title

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

Example: Input: “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.

Analysis of the following scheme 1: start to end with a two-layer loop character alignment, time complexity O(n²), not recommended scheme 2: I came up with an integer array, subscript the corresponding character ASCII code, and then value the array position of the latest occurrence of the character. Here I use len for the current cumulative length, I for the position of the character in the character array, and tag for the start position of the current substring. Doing so requires only one traversal of the character array, O(n) time.

C language solution is as follows

int lengthOfLongestSubstring(char * s){
    // Common ASCII characters range from 0 to 128, which is more than enough to open an array of 150
    int tem[150] = {0};
    int len = 0,i=1,result=0,tag=0;
    while(*s ! ='\ 0') {int a = s[0];
        if(tem[a]==NULL || tem[a]<tag){
            tem[a] = i; // Marks the last location where the character exists
            len++;
        }else{ result=len>result? len:result; tag=tem[a]; len=i-tag- 1;
            tem[a]=NULL;
            continue;
        }
        s++;
        i++;
    }
    returnlen>result? len:result; }Copy the code

The result of the final commit is as follows, and you can see that the algorithm can be further optimized: execution time: 4 ms, beat 84.91% of users memory consumption: 5.5 MB in all C commits, beat 100.00% of users in all C commits