最长不含重复字符串的子字符串

落日映苍穹つ 2024-02-19 19:27 54阅读 0赞

一、题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含′a′′a′~′z′′z′的字符。例如，在字符串"arabcacfr""arabcacfr"中，最长的不含重复字符的子字符串是"rabc""rabc"或者"acfr""acfr"，长度为4.  
二、解题思路

1.采用动态规划求解  
定义函数f(i)f(i)表示第ii个字符为结尾的不包含重复字符的子字符串的最大长度。  
如果第ii个字符在0~(i-1)位置没有出现过，那么有f(i)=f(i−1)+1;

如果第ii个字符在之前出现出，且距离它上一次出现的位置有距离d<=f(i−1)，那么可以得到f(i)=d;

如果第ii个字符在之前出现过，且距离它上一次出现的位置有距离d>f(i−1)，那么可以得到f(i)=f(i)+1；

代码：

// 最长不含重复字符的子字符串
    int longestSubstringWithoutDuplication(const string& str)
    {
        if (str.empty())
            return 0;
        int len = str.length();
        vector<int> dp(len);
        dp[0] = 1;
        auto maxx = 1;
        // 建立一个字母哈希来保存当前的字母上一次的位置
        vector<int> last_pos(26,-1);    
        last_pos[str[0] - 'a'] = 0;
        for (auto i = 1; i < len; i++)
        {
            auto lastPos = last_pos[str[i] - 'a'];
            if (lastPos >= 0)
            {
                if ((i - lastPos) <= dp[i - 1])
                    dp[i] = i - lastPos;
                else
                    dp[i] = dp[i - 1] + 1;
            }
            else
                dp[i] = dp[i - 1] + 1;
            // 存下每个字母本次出现的位置
            last_pos[str[i] - 'a'] = i;
            maxx = max(maxx, dp[i]);
        }
        return maxx;
    }

2、使用位图及快慢指针

使用位图（不知道位图可以点这里）及快慢指针来查找子串，位图存储快慢指针之间的字符。  
使用快慢指针：  
（1）慢指针不动，快指针先走，每走一步，判断快指针所指字符在位图中是否已经存在，不存在，存储字符信息并继续走，直到快指针指向重复字符串;  
（2）若此时快指针 - 慢指针 > 已经记录的字符串长度，更新字符串长度；  
（3）快指针不动，慢指针开始走，每走一步，将位图中对应的字符信息删除，直至快慢指针所指的字符相同（此时快慢指针依旧是错开的，慢指针指向快指针这个字符出现的第一次，快指针指向的是字符出现第二次），此时不删除该字符的信息，慢指针直接加加；  
（4）重复步骤（1）、（2）、（3），直至快指针走到字符串尾，当快指针指向尾，再判断一次步骤2，返回子串串长度。

int lengthOfLongestSubstring(char* s) {
        assert(s);
        int count = 0;
        char* start = s;
        char* end = s;
        char bitmap[255] = { 0 };//并没有真的用位图，只是位图的思想
        while (*end != '\0')
        {
            if (bitmap[*end] == 0)
            {
                //走快指针，将字符信息置1
                bitmap[*end] = 1;
            }
            else
            {
                if (end - start > count)
                {
                    count = end - start;
                }
                while (*start != *end)
                {
                    //移动慢指针start，将字符信息置0
                    bitmap[*start] = 0;
                    start++;
                }
                start++;
            }
            end++;
        }
        if (end - start > count)
        {
            //最后需要判断一遍，因为快指针指向尾的那一次并没有比较长度
            count = end - start;
        }
        return count;
    }