Search code examples
c++stdstring

LeetCode findAnagrams: addition of unsigned offset error


I am getting the following error when submitting the following code to leetcode, I dont know why, as the code runs fine on my local machine. How can I reproduce this error and figure out exactly what's causing it?

Line 1061: Char 9: runtime error: addition of unsigned offset to 0x7ffdd1b0d720 overflowed to 0x7ffdd1b0d71e (basic_string.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/basic_string.h:1070:9
bool find_match(const std::map<char, std::pair<int, int>> &m){
  for(const auto& [k, v] : m){
    if(v.first != v.second) return false;
  }
  return true;
}

std::vector<int> findAnagrams(std::string s, std::string p){
  std::vector<int> result;
  std::map<char, std::pair<int, int>> search;
  for(const char& c : p){
    search[c].first++;
    search[c].second = 0;
  }

  for(int i = 0; i < s.size(); i++){
    if(p.find(s[i]) != p.npos)
      search[s[i]].second++;
    
    if(find_match(search))
      result.push_back(1 + i - p.size());

    if((1 + i - p.size() >= 0) && (p.find(s[1 + i - p.size()]) != p.npos))
      search[s[1 + i - p.size()]].second--;
  }

  return result;
}

Solution

  • Store length of the string p at the beginning , then use that.

    vector<int> findAnagrams(string s, string p)
    {
        int pLen = p.size();
        ....
    }
    

    Replace all p.size() in your code with pLen. Then you're good to go.

    Just like Mr. Sam Varshavchik explained in comment section, 1 + i - p.size() >= 0 this is causing the error.

    You can print the value of 1 + i - p.size() >= 0 in leetcode, you'll be able to see the error.