算法优化问题

Question

代码优化问题。给定一个字符串，找到最长的子串的长度不重复字符。例如字符串是"abcabc"那么应该返回3，如果是"bbbb"应该返回1
跑的时候总说时间过长

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        int n = 0;
            if (s == "")
            {
                return n;
            }
            else
            {
                char[] chr = s.ToCharArray();
                for (int i = 0; i < chr.Length; i++)
                {
                    for (int j = i + 1; j < chr.Length; j++)
                    {
                        if (chr[i] == chr[j])
                        {
                            n = j;
                        }
                    }
                }
            }
            return n;
    }
}

Answer 1

O(N)可以解决这个问题。

假设last[c]表示字符c上次出现的位置，
dp[i]表示以s[i]结尾的不重复字符串的最大长度。

对于dp[i]的计算，有两个限制，一是它最左边至多延伸到last[s[i]]的位置，
二是它最多延伸到dp[i - 1]所能延伸到的位置，两个候选解选择最短的那个就可以了。

时间复杂度O(N)，下面是c++的实现，跟c#大同小异。

如果想输出那个子串，根据最大长度和取最优解的位置就能够恢复出来。

#include <bits/stdc++.h>
using namespace std;
int longest(string s) {
    if (s.size() <= 1) {
        return s.size();
    }
    vector<int> last(26, -1);
    vector<int> dp(s.size(), 1);
    int res = 1;
    last[s[0] - 'a'] = 0;
    for (int i = 1; i < (int)s.size(); ++i) {
        dp[i] = min(dp[i - 1] + 1, i - last[s[i] - 'a']);
        last[s[i] - 'a'] = i;
        res = max(res, dp[i]);
    }
    return res;
}
int main() {
    // 3
    printf("%d\n", longest("abcabc"));
    // 1
    printf("%d\n", longest("bbb"));
    return 0;
}