Stack buffer overflow error while submitting solution on leetcode

Question

I am trying to submit my solution on leetcode, when I submit it it gives me a run time error.

AddressSanitizer: stack-buffer-overflow on address 0x7ffd6484f411 at pc 0x000000386795 bp 0x7ffd6484ed70 sp 0x7ffd6484ed68

Here is my code:

int lengthOfLongestSubstring(std::string s)
{
    auto start = std::begin(s);
    std::string substring = std::string(std::begin(s), std::begin(s) + 1);
    std::string pre_string = std::string(std::begin(s), std::begin(s) + 1);
    for (auto itr = std::begin(s) + 1; itr != std::end(s); ++itr)
    {
        auto next = itr;
        if (std::find(std::begin(substring), std::end(substring), *itr) ==
            std::end(substring))
        {
            substring = std::string(start, itr + 1);
        }
        else
        {
            if (++next != std::end(s))
            {
                start = itr;
                pre_string = substring;
                substring = std::string(itr, ++itr);
            }
        }
    }

    if (pre_string.length() > substring.length())
    {
        return pre_string.length();
    }
    else
        return substring.length();
}

when I try to run it on my machine, It does not give me any warning. It's running totally fine. I am using the following command. g++ -Wall -Wpedantic longestString.cpp -o long.o

and further I used valgrind to see the any problem but it also says there is no problem as you can see the output.

username@droozal:~/leetcode$ valgrind ./long.o
==9473== Memcheck, a memory error detector
==9473== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==9473== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==9473== Command: ./long.o
==9473== 
5
==9473== 
==9473== HEAP SUMMARY:
==9473==     in use at exit: 0 bytes in 0 blocks
==9473==   total heap usage: 2 allocs, 2 frees, 73,728 bytes allocated
==9473== 
==9473== All heap blocks were freed -- no leaks are possible
==9473== 
==9473== For counts of detected and suppressed errors, rerun with: -v
==9473== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

so my question is what can be the potential error? is something broken in my code Or what? Answers will be appreciated. Thanks.

Btw, STL [is not](https://stackoverflow.com/questions/5205491/whats-the-difference-between-stl-and-c-standard-library) the standard library, and `std::string` was not part of STL. — Evg, Jul 06 '20 at 07:00
This is a very common misconception. Many people add STL tag for something that has (almost) no relation to it. — Evg, Jul 06 '20 at 07:03
@MohsanAli [What's the difference between “STL” and “C++ Standard Library”?](https://stackoverflow.com/questions/5205491) — t.niese, Jul 06 '20 at 07:04
The evaluation order of function arguments is unspecified. Don't do `std::string(itr, ++itr)`. (I suspect that it even has undefined behaviour.) — molbdnilo, Jul 06 '20 at 07:16

score 0 · Answer 1 · edited Jul 27 '20 at 12:44

I see that you're trying to solve with constant memory, I guess. You can use memoization though for this problem, much simpler to code/debug.

This'll pass through:

#include <string>
#include <map>
#include <algorithm>

class Solution {
public:
    static inline int lengthOfLongestSubstring(const std::string s) {
        map<char, int> char_map;
        int start = -1;
        int longest = 0;
        const int length = s.size();
        for (int index = 0; index < length; index++) {
            if (char_map.count(s[index]) != 0) {
                start = std::max(start, char_map[s[index]]);
            }

            char_map[s[index]] = index;
            longest = std::max(longest, index - start);

        }

        return longest;
    }
};

References

For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2} in there.

Stack buffer overflow error while submitting solution on leetcode

1 Answers1

References