题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 数据范围:s.length≤40000


题解:动态规划

哈希表统计: 遍历字符串 s 时,使用哈希表(记为 dic )统计 各字符最后一次出现的索引位置 。 左边界 i

获取方式: 遍历到 s[j]时,可通过访问哈希表 dic[s[j]]获取最近的相同字符的索引 i。

复杂度分析: 时间复杂度 O(N) : 其中 N 为字符串长度,动态规划需遍历计算 dp 列表。

空间复杂度 O(1) :字符的 ASCII 码范围为 0 ~ 127 ,哈希表 dic 最多使用 O(128) = O(1) 大小的额外空间

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        // write code here
        vector<int> dp(128,-1); //字符的 ASCII 码范围为 0 ~ 127
        int maxlen=0;  //最大长度结果
        int begin = -1; //起始值设置位-1,字符的 ASCII 码范围为 0 ~ 127
        for(int i =0;i<s.size();i++){
            if(dp[s[i]]>begin) //存在
                begin = dp[s[i]];
            dp[s[i]] = i;
            maxlen = max(maxlen,i-begin);
        }
        return maxlen;
    }
};