首页 > 代码库 > leetcode-Longest Substring Without Repeating Characters 最长不重复子串

leetcode-Longest Substring Without Repeating Characters 最长不重复子串

2024-07-10 16:18:42   223人阅读

在一个字符串中求不重复子串的最大长度是一个经典的贪心法求解问题（说子串自然是连续的，子序列则不要求连续）。

先给出leetcode上这题的描述：

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.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> um;//um记录遍历过程中每个字符最后出现的位置
        int res=0,i=0,j=0; //j记录当前不重复子串的起点，i记录当前不重复子串的终点

        while(i<s.size()){ //遍历字符串
            if(um.find(s[i])!=um.end() && um[s[i]]>=j ) //如果当前维护的不重复子串中出现了s[i]
                j=um[s[i]]+1;   //更新j
            else  //如果当前维护的不重复子串中没有出现s[i]
                res=max(res,i-j+1); //更新结果，取较大者

            um[s[i]]=i; //更新um
            i++;
        }
        return res;
    }
};
       算法时间复杂度O(n)，空间复杂度O(1)。因为ASCLL码字符个数128个，这里用unorder_map打表记录每个字符在字符串中最后出现的位置，unordered_map的空间消耗最大为128，所以时间复杂度是常数级的。unordered_map的查找插入操作的时间复杂度都是O(1)，所以整个算法的时间度为O(n)。

        需要注意的是，unordered_map是无序容器，在找是否出现重复字符的时候，一定要在当前考察的子串的范围内查找，所以条件 && um[s[i]]  >= j不能漏。当然这里也可以用一个128长度的数组替换unordered_map，好处是数组时有序的。见以下代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hs[128];
        int res=0,i=0,j=0; 
        memset(hs,-1,128*sizeof(int));
        
        while(i<s.size()){ 
            if( hs[s[i]-0]>=j ) 
                j=hs[s[i]-0]+1;   
            else  
                res=max(res,i-j+1); 

            hs[s[i]-0]=i; 
            i++;
        }
        return res;
    }
};


联系
我们