c++pointerssliding-window

Finding longest substring without repeating characters


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.


Solution

  • 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.