Count Substrings

Count how many times a substring appears in a string without overlapping.

strings counting substrings

Write a function `count_substrings(s: str, sub: str) -> int` that returns the number of **non-overlapping** occurrences of the substring `sub` in the string `s`. Occurrences are counted by scanning from left to right, and after a match is found, the search continues after the end of that match. For example, in `"aaaa"` with `sub = "aa"`, the first match covers indices 0-1, the next match starts at index 2, so the result is 2, not 3. If `sub` is an empty string, the function should return 0. The function should handle any valid Python strings.

Constraints

`0 <= len(s) <= 10^5`, `0 <= len(sub) <= 10^5`. The function should run in O(len(s) * len(sub)) or better. The expected output is an integer.

Example

>>> count_substrings("hello world", "l")
3
>>> count_substrings("aaaa", "aa")
2
>>> count_substrings("abcabcabc", "abc")
3
>>> count_substrings("", "a")
0

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Consider using `str.find(sub, start)` in a loop, updating the start position after each match.

Remember that occurrences must be non-overlapping: after a match, continue searching after the end of the match.

An empty `sub` is a special case; you should return 0 for it.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.