Why it works
- The window is always as long as the needle and moves one letter at a time, so every place the needle could start is checked, the first one first.
- If the sums differ, the letters differ: such a window is skipped in O(1). The sum is updated like a running sum, one code in and one out.
- Equal sums do not mean equal letters ("cbb" and "bad" both make 7), so a window with the right sum is still compared letter by letter.
Complexity
Time: the sums take O(n + m), plus O(m) for each window whose sum matches. With few false alarms that is O(n + m); in the worst case, when nearly every window has the right sum, O(n · m). Memory O(1).
nextNow solve it yourself, no hints.
Solve on LeetCode ↗