【算法设计与分析作业题】第三周:3. Longest Substring Without Repeating Characters
题目
C++ solution
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int result = 0;
int len = s.size();
for (int i = 0, j = 0; j < len; ++j)
{
for (int k = i; k < j; ++k)
{
if (s[k] == s[j])
{
i = k + 1;
}
}
if(result < (j - i + 1))
result = j - i + 1;
}
return result;
}
};
简要题解
- 变量 i,j 分别为 substring 在原 string 的头尾下标
- 检查新增的字符s[j] 在 substring 中是否存在
- 若存在,则将 substring 中重复字符的下标加1,赋值给i
- 更新目前最长的 substring 长度,递增 j;若 j 等于string长度,则结束循环,否则,循环步骤2,3,4