I'm trying to solve LeetCode 3: Longest Substring Without Repeating Characters.
I'm implementing the Sliding Window method, which consists of using a left and a right pointer to contract and expand the window. I'm also using a std::set
to store the characters of the string.
#include <iostream>
#include <set>
#include <algorithm> //for std::max()
//Sliding window
int lengthOfLongestSubstring(std::string s)
{
std::set<char> charSet;
int length = s.size();
int left = 0;
int right;
int longest = 0; //value we should return
for(right = 0; right < length; right++)
{
char c = s[right]; //get each element of the string
//if character already exist in the set
while (charSet.count(c)) //while we found a character that is a duplicate, we'll contract the window by increase the left pointer + 1
{
charSet.erase(s[left]); //removing the element where left pointer is pointing at
left += 1; //increase the left pointer
}
charSet.insert(c); //store the current element into the set
int w = left - right + 1; //calculate window length
longest = std::max(longest, w); //update longest with longest current window length
}
return longest;
}
int main()
{
std::string s{"abcabcbb"};
std::cout << lengthOfLongestSubstring(s);
return 0;
}
Output:
2
The correct output should be 3.
Basically your code have silly mistake in this line:
int w = left - right + 1; //calculate window length
https://godbolt.org/z/nPs3GvfqE
Correcting that to:
int w = right - left + 1; //calculate window length
and tests are passing: https://godbolt.org/z/sfqzvhbc8
Anyway there is better faster solution, with this I've got 0 time (100% faster then others) and using less memory then 93.55% of other submissions.