leetcode 3 -- Longest Substring Without Repeating Characters

leetcode 3 – Longest Substring Without Repeating Characters

题目：
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

---

题意：
给予一个字符串，找出最长的且不重复的字串，返回长度。比如”abcabcbb”，那么最长的且没有重复字符的是”abc”，长度为3。如果是”abca”，就不满足要求了，因为重复出现了字母a。

---

思路：用普通的匹配方法时间复杂度大约是O(n^3)，肯定是不满足的，解决方案是用类似滑动窗口圈出子串(substring)在原字符串上移动，用hashtable做辅助看哪些字母是出现过的，且映射的是出现过的字母的下标（方便一会快速跳转，有点类似KMP），如果字母未出现在hashtable，说明子串可以增长，如果出现过了说明有重复的不满足条件，需要将圈出子串的滑动窗口滑动，滑动的位置大小就是hashtable存储此字母曾经出现过的下标，算法时间复杂度是O(n)。

---

代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret_size = 0;
        int j = -1;
        int hash[256];
        memset(hash, -1, sizeof(hash));
        for(int i = 0; i < s.size();i++){
            //说明s[i]出现过
            if(hash[s[i]] > j){
                //i(右)和j(左)就相当于滑动窗口的边界，改变i,j值就是移动滑动窗口
                j = hash[s[i]];
            }
            //比较并更新返回值
            if(i-j > ret_size){
                ret_size = i-j;
            }
            //记录出现过的下标
            hash[s[i]] = i;
        }
        return ret_size;
    }
};

---

补充：上面的题是求字符串最长且没有重复的字串长度，补充一个类似的题，求字符串最长且重复的字串长度，比如”abcabcbb”，那么最长的且重复出现过的是”abc”。

---

思路：用后缀数组求解，建立从不同起点到相同终点的字符串子串，用指针数组即可，然后排序这些指向字符串的指针，比较相邻的公共长度即可。

---

代码：

//比较函数
static int 
compare(const void *p1, const void *p2){
    return strcmp(*(char*const*)p1, *(char*const*)p2);
}

//比较相同长度的函数
int cmp_same(char *p1, char *p2){
    int ret = 0;
    while(*p1 != '\0' && *p2 != '\0'){
        if(*p1 == *p2){
            ++p1;
            ++p2;
            ++ret;
        }
    }
    return ret;
}

int lengthOfLongestSubstring(char* s) {
    const int num = strlen(s);
    //指针数组
    char *p[num];
    int i = 0;
    int ret_size = 0;
    int t = 0;
    //指针数组初始化
    for(i = 0; i < num; ++i){
        p[i] = s+i;
    }
    //排序指向字符串的指针
    qsort(p, num, sizeof(char*), compare); 
    for(i = 0; i < num-1; ++i){
        //找到公共前缀
        t = cmp_same(p[i], p[i+1]);
        if(t > ret_size){
            ret_size = t;
        }
    }
    return ret_size;
}

---

字符串的题也可以考虑下tries树，包括前缀树和后缀树。