Leetcode 003 Longest Substring without repeating characters

Leetcode 003 题

Difficulty:medium

Tag: dp

题目

Given a string, find the length of the longest substring without repeating characters.

找出字符串中最长的不包含重复字符的子串。

例子

"abbac"  bac
"abcabcbb" abc
"bbbbb" b
"pwwkew" wke
"c" c

思路

动态规划

设 $dp[i] = s[m]…s[i]$ 是最长的不包含重复字符的子串，且以 $s[i]$ 结尾。

接下来看字符$s[i + 1]$

若 s[i + 1]在之前出现过，设其下标为$k$。此时需要知道下标为k的字符是否在$dp[i]$内

如果在，k >= m ,需将 m 更新为 k + 1, 此时$dp[i + 1] = s[k + 1]…s[i + 1]$

如果不在，k < m，无需更新 m，此时$dp[i + 1] = s[m]…s[i + 1]$

综上，若 s[i + 1]在之前出现过，设其下标为$k$。此时的递推方程为 $m = max(m, k), dp[i + 1] = s[m]…s[i + 1]$

若 s[i + 1] 在前没有出现过，直接将s[i + 1]加到dp[i]即可 $dp[i + 1] = s[m]…s[i + 1]$

实现

动态规划是一种思想，所以具体实现的时候还是需要一定的数据结构支持。

这里有的数据结构有：

1. 字典，key = s[i] value = i, 用来表示某个字符是否出现过。可以是C++ map对象，由于本题只有字符，所以可以使用一个数组来代替，具体可以参考代码实现。
2. 两个指针l , r，r用来向前扫描字符，l来用指定子串的在s中的起始位置。

更新过程：

维护字典，r向前扫描字符的过程中查看当前字符是否在字典中，不在，插入，在，更新l.

code 1

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> index;
        int len = 0;
        for(int r = 0, l = 0; r < s.length(); r++)
        {
            if(index.find(s[r]) != index.end())
            {
                l = max(l, index[s[r]] + 1);
            }
            index[s[r]] = r;
            len = max(len, r - l + 1);
        }
        return len;
    }
};

更为直接的，通过设置index的初始值，可以显式的省略 字典的查找操作。

code 2

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //int index[128] = {-1};
        vector<int> index(128, -1);
        int m = 0;
        int len = 0;
        for(int i = 0; i < s.length(); i++)
        {
            m = max(index[s[i]] + 1, m);
            index[s[i]] = i;
            len = max(len, i - m + 1);
        }
        return len;
    }
};