3. Longest substring without repeating characters

What is a sliding window ？

It's actually a queue , For example, in the example abcabcbb, Enter this line （ window ） by abc Meet the requirements of the topic , When you enter a, The queue becomes abca, Not meeting the requirements at this time . therefore , We're going to move this queue ！

How to move ？

All we have to do is move the elements on the left side of the queue , Until the subject requirements are met ！ Keep this line up all the time , Find out the maximum length of the queue , Find out the solution ！

Time complexity ：O(n).

Java resolvent

A data structure is needed to determine whether there are repeated characters ：HashSet.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> ss = new HashSet<Character>();
        int slen = s.length();
        int length = 0;
        int maxLength = 0;
        for(int i = 0; i < slen; i++)
        {
            // Exit an element in the queue 
            if(i != 0)
            {
                ss.remove(s.charAt(i - 1));
            }
            // Add elements to the queue , join HashSet Will automatically determine whether there is repetition 
            while(length < slen  && ss.add(s.charAt(length)))
            {
                length++;
            }
            if(maxLength < length - i)
            {
                maxLength = length - i;
            }
        }
        return maxLength;
    }
}

C Language solutions

bool haveSame(char *ss, int start, int end, char c)
{
    int i = start;
    if(end == 0)
    {
        return true;
    }
    while(i < end && ss[i] != c)
    {
        i++;
    }
    if(i >= end)
    {
        return true;
    }
    else
    {
        return false;
    }
}
int lengthOfLongestSubstring(char * s){
    char *ss = NULL;
    int len;
    len = strlen(s);
    ss = (char *)malloc(len * sizeof(char));
    int length = 0;
    int maxLength = 0;
    for(int i = 0; i < len; i++)
    {
        // Add elements to the queue , join HashSet Will automatically determine whether there is repetition 
        while(length < len  && haveSame(ss, i, length, s[length]))
        {
            ss[length] = s[length];
            length++;
        }
        if(maxLength < length - i)
        {
            maxLength = length - i;
        }
    }
    return maxLength;
}