LeetCode 3

Longest Substring Without Repeating Characters

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

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

简述：统计字符串不重复字符最长子串的长度。

C语言实现

使用两个下标i，index。i作为字符串的下标，依次往下移动。index为子串的下标往右移动。index+i是在母串移动的位置。
初始化子串p比母串大1，不然有的编译器报越界。每次赋值后给下一位赋值'\0'，

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

int isInclude(char *s, char a) {
    while (*s != '\0') {
        if (*s == a) {
            return 1;
        }
        s++;
    }
    return 0;
}

void clear(char *s) {
    while (*s != '\0') {
        *s = '\0';
        s++;
    }
}

int lengthOfLongestSubstring(char *s) {
    int i = 0, max = 0;
    int index = 0;
    char p[strlen(s) > 0 ? strlen(s)+1 : 1];

    while (s[i] != '\0') {
        if (!isInclude(p, s[i + index])) {
            p[index] = s[i + index];
            p[index+1] = '\0';
            index++;

            if (index >= max) {
                max = index;
            }

            if (s[index + i] == '\0') {
                break;
            }
        } else {
            index = 0;
            clear(p);
            i++;
        }

    }
    return max;

}

int main() {
    char *s = "vfqsrebtogjmcanajfyzvypzibtngtrca";

    int length = lengthOfLongestSubstring(s);
    printf("LongestLength=%d\n", length);
    return 0;
}

因为C语言没有现成使用的集合类，如（Map,Set），书写起来较为复杂。算法复杂度也挺高。下图为执行耗时，比较不理想。

image.png

时间复杂度：

遍历母串加子串移动n(n-1) ，找到一个字符需要从头查找比对。最坏情况为，n(n-1)*n ，时间复杂度O(n^3)

空间复杂度：
O(n)+1

Java实现（使用Set实现）

通过集合Set的特性集合中不能出现重复值，检测子串在Set中是否存在，存在的话把集合里面连同本身及之前的元素全部去掉。这种方式被称为SLIDING WINDOW(滑动窗口)

 //最初实现
    public int lengthOfLongestSubstring_2(String s) {

        int max = 0;
        int i = 0, j = 0;
        Set<Character> set = new HashSet<>();

        while (i < s.length() && j < s.length()) {

            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                max = Math.max(max, j - i);
            } else {
                set.remove(s.charAt(i++));
            }
        }
        return max;
    }

执行流程如下：String s = "abcaea"

i	set	j	max	j - i
0	a	1	1	1
0	a,b	2	2	2
0	a,b,c	3	3	3
1	b,c	3	3	2
1	b,c,a	4	4	3
1	b,c,a,e	5	4	4
2	c,a,e	5	4	3
3	a,e	5	4	2
4	e	5	4	1
4	ea	6	4	2

算法复杂度 O(2n) =O(n)
空间复杂度 O(n)

Java实现(HashMap 优化)

使用HashMap自动覆盖重复的key相同的value，记录下每个字符在字符串中出现的最后位置。使用i记录不重复字符子串的起点，j-i-1表示字符串的长度。出现重复字符是更新i的位置。

 //HashMap
    public int lengthOfLongestSubstring_3(String s) {

        Map<Character,Integer> map = new HashMap<>();

        int max = 0;

        for (int i = 0,j=0; j < s.length(); j++) {
            if (map.containsKey(s.charAt(j))){
                i = Math.max(map.get(s.charAt(j)),i);
            }

            max = Math.max(max, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return max;
    }

时间复杂度：O(n)
空间复杂度：O(n)
效率比HashSet快的原因是，没有对字符移除的操作，并且HashMap的查询速率把HashSet更快。

Java实现 (使用ASCII 128）

标准ASCll表示从0-127表示128个字符，通过字符代表ASCll值字符位置，数组中存储的是每个字符在字符串中出现的最后位置。是对HashMap实现的优化。因为没有了查询耗时，这种的执行效率最好。

 public int lengthOfLongestSubstring_4(String s) {
        
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        
        
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        
        
        return ans;
    }

时间复杂度：O(n)
空间复杂度：O(n)