LeetCode 问题 3：无重复字符的最长子串

Question

此题尝试：

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

以及示例：

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

我的代码是：

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 );
}

对于给定的字符串 "nfpdmpi"，我可以在本地 PC 上得到正确的输出 = 5。

但是我把代码提交到LeetCode网站上，它说我的输出是6。

怎么了？

Answer 1

这一行：

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

从无序集中删除一个范围。由于未定义顺序，这可以擦除任意数量的元素，包括一个元素。这可能是结果不同的原因。 ~~相反，您想做~~

~~sub.clear();~~

~~因为您想开始识别一个全新的子字符串。~~

编辑：

这不是正确的解决方案。这是一个带有自定义比较器的有序集合：

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());
}

编辑 2：修复了擦除行以从开始到找到的字符擦除而不是从找到的字符到结束。

LeetCode 问题 3：无重复字符的最长子串

LeetCode Problem3: Longest Substring Without Repeating Characters

c++

substring

string-length