LeetCode Problem3: Longest Substring Without Repeating Characters

Question

This problem is try to:

Given a string, find the length of the longest substring without repeating characters.

And the example:

Given "nfpdmpi", the answer is "nfpdm", which the length is 5.

And my code is:

int lengthOfLongestSubstring(string s) {
    unordered_set<char> sub;
    size_t max_len = 0;

    for (int i=0 ; i<s.size() ; ++i) {
        if ( sub.find(s[i]) != sub.end() ) {
            max_len = ( sub.size() > max_len ? sub.size() : max_len );
            sub.erase( sub.find(s[i]), sub.end() );
        }

        sub.insert(s[i]);
    }

    return ( sub.size() > max_len ? sub.size() : max_len );
}

For the given string "nfpdmpi", I can get the correct output = 5 on my local PC.

But I submit the code onto LeetCode website, and it said my output is 6.

What's going wrong?

Answer 1

This line:

sub.erase( sub.find(s[i]), sub.end() );

erases a range from an unordered set. Since the order is not defined, this can erase any number of elements including only one. This is probably the reason why results differ. Instead, you want to do

sub.clear();

because you want to start recognizing a completely new substring.

Edit:

That was not a correct solution. Here's one with an ordered set with custom comparator:

struct char_occurrence_comp {
  static int lastpos[255];
  bool operator() (const char& lhs, const char& rhs) {
    return lastpos[static_cast<int>(lhs)] < lastpos[static_cast<int>(rhs)];
  }
};
int char_occurrence_comp::lastpos[255] = {}; // initialize with 0

int lengthOfLongestSubstring(const std::string& s) {
  std::set<char, char_occurrence_comp> sub;
  std::size_t max_len = 0;
  for (std::size_t i = 0; i < s.size(); ++i) {
    const auto iter = sub.find(s[i]); 
    if ( iter != sub.end() ) {
      max_len = std::max(max_len, sub.size());
      // end is exclusive, so we need to advance the iterator.
      sub.erase(sub.begin(), std::next(iter, 1));
    }
    // make sure we do not hit the default value (0)
    char_occurrence_comp::lastpos[static_cast<int>(s[i])] = i + 1;
    sub.insert(s[i]);
  }
  return std::max(max_len, sub.size());
}

Edit 2: Fixed the erase line to erase from start to found char instead of from found char to end.