3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

解法

滑动窗口

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int longestSubstring(char *s);
int max(int a, int b);

int main()
{
    char *s = "abcabcbb";
    int length;

    length = longestSubstring(s);
    printf("The length of longest substring is: %d\n", length);

    return 0;
}

int longestSubstring(char *s)
{
    int start,end;
    int len = strlen(s); // 字符串长度
    int lenW; // 滑动窗口长度
    char window[128]; // 滑动窗口内的字符
    int pos[128]; // 滑动窗口内的字符在原字符串的位置
    int p,i,flag;
    int length = 0;

    memset(window,0,128*sizeof(char));
    memset(pos,0,128*sizeof(int));
    
    for (start = 0, end = 0; end < len; end++)
    {
        flag = 0;
        p = 0;
        lenW = strlen(window);
        for (i = 0; i < lenW; i++)
        {
            if (window[i] == s[end])
            {
                flag = 1;
                p = pos[i];
                break;
            }
        }
        if (flag)
        {
            start = p + 1;
        }

        length = max(length, end-start+1);
        
        memset(window,0,128*sizeof(char));
        memset(pos,0,128*sizeof(int));
        for (i = 0, p = start; p <= end; p++)
        {
            window[i] = s[p];
            pos[i] = p;
            i++;
        }
    }
    
    return length;
}

int max(int a, int b)
{
    return a > b ? a : b;
}