23-Longest Substring Without Repeating Characters
2024-09-08 13:32:59
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
本题:中等难度
思路:动态规划
f[j]表示以j结尾的无重复子串的最大长度
f[j]={f[j−1]+1f[j−1]−num+1A[j]notinvs[j−1]A[j]invs[j−1]
其中vs[j-1]保存连续子串,num表示去掉重复字符(包含)之前的字符$$
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
if(n<=1)return n;
vector<vector<char> > vm(n);
vector<int> vi(n);
vi[0]=1;
vm[0].push_back(s[0]);
for(int i=1;i<n;++i)
{
vector<char>::iterator it= find(vm[i-1].begin(),vm[i-1].end(),s[i]);
if(it!=vm[i-1].end())
{
vector<char> vtmp(it+1,vm[i-1].end());
vm[i]=vtmp;
vm[i].push_back(s[i]);
vi[i]=vm[i-1].end()-it;
}
else{
vi[i]=vi[i-1]+1;
vm[i]=vm[i-1];
vm[i].push_back(s[i]);
}
}
return *max_element(vi.begin(),vi.end());
}
};
最新文章
- 点燃圣火! Ember.js 的初学者指南
- 字符串模板替换方法 MessageFormat.format
- I Hate It(线段数组基础题)
- jdbc 连接 mysql 获取 数据集 条数
- C# winform 最小化到电脑右下角
- Python 命令行非阻塞输入
- rpc和websocket的区别
- osg复制多个相同物体修改材质属性问题
- Linux安装JDK步骤
- 开启irqbalance提升服务器性能
- docker使用代理(测试docker 17.06)
- 异常 Exception 知识点总结 MD
- centos5&;6的启动过程
- CSS表单2 组件排版
- [模板]LCA
- 报错ORA-19809 ORA-19804
- auxre7使用安装
- CF1065E Side Transmutations
- Python之进度条
- 乱码之UTF-8 &;GBK