DEV Community

Discussion on: Advent of code Day 2 Part 2 Complexity

themindfuldev profile image
Tiago Romero Garcia

Gotcha! It’s great to challenge ourselves to see if we can go one step beyond. Please let me know if you can find out something!

One limitation that I just thought with this algorithm is that it had been originally used to search subsequent characters inside a bigger string. But in our case, any char can be different, so we might need to look at the whole substring (which happens to have the same size as every other string) and hence maybe we won’t be able to get down to O(N).

But maybe there’s a way to create a very clever hash function that would work regardless of this limitation so we don’t need to manually compare each char. But I might be overlooking this.