代码优化问题。给定一个字符串,找到最长的子串的长度不重复字符。例如字符串是"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;
}
}
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;
}