class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<string> all_sub; // store all unduplicated substrings
for (size_t start = 0; start < s.size(); start++){
set<char> myset;
string res; // longest substring starting at "start"
for (size_t end = start; end < s.size(); end++){
if (myset.find(s[end]) == myset.end()){
// this char has not been seen before
res.push_back(s[end]);
myset.insert(s[end]);
}
else {
// this char has seen before
break;
}
}
all_sub.push_back(res);
}
// find the longest among all substrings
int longest = 0;
for (auto & r : all_sub){
if (r.size() > longest)
longest = r.size();
}
return longest;
}
};
Uses a set. Why? A hash map cannot have " " as key...
In C++, set is a BST. So the search is O(log n) instead of O(n) as in the brute force solution.
In C++, set is a BST. So the search is O(log n) instead of O(n) as in the brute force solution.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.