3. Longest Substring Without Repeating Characters

2019-11-06 08:21:06

字体：大中小

来源：转载

供稿：网友

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.Subscribe to see which companies asked this question.

动态规划的简单应用，存储第i-1位置的最长串d[i-1],然后到第i位置，比较有s[i]的最长串和d[i-1]，取最大值

class Solution {public: int lengthOfLongestSubstring(string s) { int dp =0; for (int t = 0;t < s.size();t++) { int l = 0; vector<bool> visited(300, false); for (int i = t;i >= 0;i--) if (visited[s[i]]) break; else { l++;visited[s[i]] = true; } dp = dp > l ? dp : l; } return dp; }};

上一篇：位运算

下一篇：实战编程-回文序列