题解 | #最长不含重复字符的子字符串#

参考了动态规划的思路

#include <vector>
class Solution {
private:
    const int c_num = 128;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        // write code here

        if (s.length() < 2) return s.length();

        vector<int> last_pos_vec(c_num, -1);
        vector<int> dp(s.length(), 1);

        int longest_sub_len = 1;
        last_pos_vec[s[0]] = 0;
        for (int pos = 1; pos < s.length(); ++pos) {

            if (dp[pos - 1] >= pos - last_pos_vec[s[pos]]) 
                dp[pos] = pos - last_pos_vec[s[pos]];
            else
                dp[pos] = dp[pos - 1] + 1;

            if (dp[pos] > longest_sub_len) longest_sub_len = dp[pos];
            last_pos_vec[s[pos]] = pos;

        }

        return longest_sub_len;
    }
};