最长不重复子串

作者: 林大鹏 | 来源:发表于2017-06-20 15:21 被阅读199次

1. 问题定义

最长不重复子串:一个字符串中最长的没有重复字符的子串。
举个🌰 :

  • abcabcbb 最长子串 abc 长度为3
  • bbbbbbb 最长子串 b 长度为1
  • abdevbac 最长子串devbac长度为6

2. 暴力破解:

对于最长不重复子串问题,最粗暴的办法是: 找到所有字符串的子串,遍历每一个子串,判断它们是否是不重复的,然后从中选出最长的不重复子串。一个子串由子串的起点和终点确定,因此对于一个长度为n的字符串,共有n^2个子串。这些子串的平均长度大约为n/2,因此这种解法的时间复杂度是O(n^3);

解法:

    string lengthOfLongestSubstring (string &s){
        if (s.empty()) {
            return "";
        }
    
        if (s.size() == 1) {
            return s;
        }
    
        // 字符串 长度
        unsigned long length = s.size();
        // 最长 无重复 字符串 长度
        int maxLength = 0;
        // 最长 无重复 字符串 起始地址
        int start = 0;

        // 外面 两层 循环 主要 遍历 每一个 子串
        for (int i = 0;  i < length; i++) {
            for (int j = i+1; j < length; j++) {
                bool isRepeat = false;
                // 判断 该 字符 在 之前 子串中 是否 存在
                for (int k = i; k < j; k++) {
                    if (s.at(k) == s.at(j)) {
                        isRepeat = true;
                    break;
                    }
                }
                // 如果 存储 跳出 循环 遍历 下一个 字符
                if (isRepeat == true) {
                    break;
                }
                // 如果 不存在 判断 并 更新
                else if(j - i > maxLength){
                    maxLength = j - i;
                    start = i;
                }
            }
        }
        return s.substr(start, maxLength+1);
    }

3. hash实现

hash实现: 两次循环得到所有的子串,通过hash值来判断是否重复。

  • 以字符对应的ASCII码作为hash值,利用数组指针visit来存储,当visit[s.at(i)] == 0, 说明这个字符还没有出现过,如果visit[s.at(j)] == 1,说明该字符出现过。
  • 再每次内层循环开始的时候,都要将visit指向的数组初始化为0,每次内层循环求的是s[i....j]之间的子串,遍历i—j的每个字符,如果字符i之前没出现过,将该字符的visit[s.at(i)] 置为1,继续遍历下个字符,如果该字符出现过,判断是否需要更新,并跳出循环。
    解法:
     string lengthOfLongestSubstring2 (string &s){
        if (s.empty()) {
            return "";
        }
    
        if (s.size() == 1) {
            return s;
        }

        // 字符串 长度
        unsigned long length = s.size();
        // 最长 无重复 字符串 长度
        int maxLength = 0;
        // 最长 无重复 字符串 起始地址
        int start = 0;
    
        int *visit = new int[256]();
        for (int i = 0; i < length; i++) {
            memset(visit, 0x00, sizeof(int[256]));
            // 该 字符 未 出现 过
            visit[s.at(i)] = 1;
            for (int j = i + 1; j < length; j++) {
                // 该 字符 未 出现 过
                if (visit[s.at(j)] == 0) {
                    visit[s.at(j)] = 1;
                }
                // 该字符 出现 过
                else {
                    if (j - i > maxLength) {
                        maxLength = j - i;
                        start = i;
                    }
                    break;
                }
            }
        }
        free(visit);
        return s.substr(start, maxLength);
    }

C语言方法:

// 最长 不重复 子串(hash方法)
int lengthOfLongestNoRepeatSubstringOne(char *string, int length) {
    if (string == NULL) {
        return 0;
    }
    if (length == 1) {
        return 1;
    }
    
    int maxSubStringLength = 1;
    int visitCharArray[256] = {0};
    
    for (int tmpFirstIndex = 0; tmpFirstIndex < length; tmpFirstIndex++) {
        visitCharArray[string[tmpFirstIndex]] = 1;
        for (int tmpSecondIndex = tmpFirstIndex + 1; tmpSecondIndex < length; tmpSecondIndex++) {
            // 该字符 没有 出现过
            if (visitCharArray[string[tmpSecondIndex]] == 0) {
                visitCharArray[string[tmpSecondIndex]] = 1;
            }
            else {
                if (tmpSecondIndex - tmpFirstIndex > maxSubStringLength) {
                    maxSubStringLength = tmpSecondIndex - tmpFirstIndex;
                }
                break;
            }
        }
    }
    
    return maxSubStringLength;
}

4. 动态规划 + hash

举个🌰 :
对于字符串"axbdebpqawuva",构造下表:

image.png
  • 表中该字符串有3a,有2b,其余为单一字符。

  • next[]记录了下一个与之重复的字符位置,如str[0] = str[8] = str[12] = 'a',这是next[0] = 8, next[8] = 12, next[12] = 13; 其余同理。

  • 值得注意的是,对于没有重复字符的,next[]存储字符结束符下标'\0',即13

  • first[i]表示i之后,第一次出现重复字符的位置,例如,str[0]之后,第一次出现重复字符是str[5] = 'b',当然从str[1], str[2]开始也是一样。而从str[3]开始,要到str[12]才出现重复字符'a'。可以证明,从str[i]的最长符合要求的长度为first[i]-i,区间为[i, first[i]-1]由此得解。上述最长串是i = 3时,first[i] - i = 12 - 3 = 9。结果串为debpqawuv
    解法:

      string lengthOfLongestSubstring4 (string &s){
        if (s.empty()) {
            return "";
        }
    
        if (s.size() == 1) {
            return s;
        }
    
        // 字符串 长度
        int length = (int)s.size();
        // 最长 无重复 字符串 长度
        int maxLength = 0;
        // 最长 无重复 字符串 起始地址
        int start = 0;
        // next[i]记录下一个与str[i]重复字符的位置
        int *next = new int[length];
        memset(next, 0, sizeof(int) * length);
        // first[i]记录str[i]后面最近一个重复点
        int *first = new int[length+1];
        memset(first, 0, sizeof(int) * (length + 1));
    
        int *visit = new int[256];
        first[length] = length;
        memset(visit, length, sizeof(int) * 256);
    
        // 倒叙 遍历 是为了计算 first和next的值
        for (int i = length - 1 ;  i >= 0; i--) {
            next[i] = visit[s[i]];
            visit[s.at(i)] = i;
            // 该 字符 出现 过
            if (next[i] < first[i+1]) {
                first[i] = next[i];
            }
            // 该 字符 未出现 过
            else {
                first[i] = first[i+1];
            }
        }
    
        for (int i = 0; i < length; i++) {
            if (first[i] - i > maxLength) {
                maxLength = first[i] - i;
                start = i;
            }
        }
    
        free(first);
        free(next);
        cout<<s.substr(start, maxLength)<<endl;
        return s.substr(start, maxLength);
      }

从代码和分析中我们可以看出,最长的无重复子串只跟first[i]数组有关,而next[i]只是作为中间变量,临时存储visit[s[i]]的值,因此next[i]可以直接用变量来代理。
解法:

    string lengthOfLongestSubstring4 (string &s){
        if (s.empty()) {
            return "";
        }
    
        if (s.size() == 1) {
            return s;
        }
    
        // 字符串 长度
        int length = (int)s.size();
        // 最长 无重复 字符串 长度
        int maxLength = 0;
        // 最长 无重复 字符串 起始地址
        int start = 0;
        int next = 0;
        // first[i]记录str[i]后面最近一个重复点
        int *first = new int[length+1];
        memset(first, 0, sizeof(int) * (length + 1));
    
        int *visit = new int[256];
        first[length] = length;
        memset(visit, length, sizeof(int) * 256);
    
        // 倒叙 遍历 是为了计算 first和next的值
        for (int i = length - 1 ;  i >= 0; i--) {
            next = visit[s[i]];
            // 存储 每个 字符的 位置
            visit[s.at(i)] = i;
            // 该 字符 出现 过
            if (next < first[i+1]) {
                first[i] = next;
            }
            // 该 字符 未出现 过
            else {
                first[i] = first[i+1];
            }
        }
    
        for (int i = 0; i < length; i++) {
            if (first[i] - i > maxLength) {
                maxLength = first[i] - i;
                start = i;
            }
        }
    
        free(first);
        cout<<s.substr(start, maxLength)<<endl;
        return s.substr(start, maxLength);
    }

C语言解法:

// 最长 不重复 子串(辅助数组 + hash)
int lengthOfLongestNoRepeatSubstringTwo(char *string, int length) {
    if (string == NULL) {
        return 0;
    }
    if (length == 1) {
        return 1;
    }
    int maxSubStringLength = 1;
    int visitCharArray[256] = {length};
    for (int tmpIndex = 0; tmpIndex < 256; tmpIndex++) {
        visitCharArray[tmpIndex] = length;
    }
    
    // 重复 数字 索引 下标
    int repeatPosition = 0;
    // 开辟 存储 重复 字符 的数组
    int *positionArray = (int *)malloc((length + 1)*sizeof(int));
    for (int tmpIndex = 0; tmpIndex <= length; tmpIndex++) {
        positionArray[tmpIndex] = length;
    }
    
    for (int tmpIndex = length - 1; tmpIndex >=0; tmpIndex--) {
        repeatPosition = visitCharArray[string[tmpIndex]];
        
        // 存储 每个 字符 的位置
        visitCharArray[string[tmpIndex]] = tmpIndex;
        
        // 该字符 出现过
        if (repeatPosition < positionArray[tmpIndex + 1]) {
            positionArray[tmpIndex] = repeatPosition;
        }
        // 该字符 没出现过
        else {
            positionArray[tmpIndex] = positionArray[tmpIndex + 1];
        }
    }
    
    for (int tmpIndex = 0; tmpIndex < length; tmpIndex++) {
        if (positionArray[tmpIndex] - tmpIndex > maxSubStringLength) {
            maxSubStringLength = positionArray[tmpIndex] - tmpIndex;
        }
    }
    return maxSubStringLength;
}

相关文章

  • 【leetcode3】 3. Longest Substrin

    关键字:最长不重复子串、双指针 难度:Medium 题目大意:求一个字符串最长不重复子串的长度 题目: Given...

  • LeetCode #1044 Longest Duplicate

    1044 Longest Duplicate Substring 最长重复子串 Description:Given...

  • 3、Longest SubString Without Repe

    Examples:找出最长无重复子串长度Given "abcabcbb", the answer is "abc"...

  • iOS面试题汇总---算法类

    字符串 【3】最长回文子串 【3】最长无重复子串 【1*】字符串转数字 【4】KMP 算法 【2】字符串全排列 【...

  • 最长不重复子串

    1. 问题定义 最长不重复子串:一个字符串中最长的没有重复字符的子串。举个? : abcabcbb 最长子串 a...

  • 寻找最长重复子串,后缀数组的方法

    寻找最长重复子串,如ask not what your country can do for you ,but w...

  • 文章收藏

    iOS面试题系列之常见算法 排序算法整理 字符串【3】最长回文子串【3】最长无重复子串【1*】字符串转数字【4】K...

  • 3、Longest Substring Without Repe

    题设 要点 双指针维护最长重复子串的位置 动态规划 寻找字符串的最长子串,就是要维护一个区间[left , rig...

  • 无重复字符串的最长子串

    题目大意:给定一个字符串,找出不含有重复字符的最长子串的长度 解读: 1、给定abcabcbb,没有重复子串的最长...

  • 最长重复子串

    前言 据统计,在所有程序中,关于字符串处理的程序占到了百分之八十以上,所以关于字符串处理的算法十分多,而且关于数字...

网友评论

    本文标题:最长不重复子串

    本文链接:https://www.haomeiwen.com/subject/bojgqxtx.html