# Non‑overlapping occurrences are matches of a substring that do not reuse any of
# the same characters. Once one match is counted, the next search must begin
# after that match ends.
def count_non_overlapping(haystack: str, needle: str) -> int:
"""
Count how many times 'needle' appears in 'haystack' without overlapping.
The algorithm:
• Use str.find() to locate the next occurrence.
• Each time a match is found, move the search index forward
by the full length of the matched substring.
• This ensures no characters are reused between matches.
"""
count = 0
index = 0 # current search position in the main string
# Continue searching until .find() returns -1 (meaning: no more matches)
while True:
# Find the next occurrence starting at the current index
pos = haystack.find(needle, index)
if pos == -1:
# No more matches found
break
# We found a match, so increment the count
count += 1
# Move index forward by the length of the needle
# This ensures the next search begins *after* the matched substring
index = pos + len(needle)
return count
# ---------------------------------------------------------------
s = 'go java phphp rust c pphpp c++ phpphp python php phphp'
substring = 'php'
# Count non-overlapping occurrences
result = count_non_overlapping(s, substring)
print("Non-overlapping occurrences:", result)
'''
run:
Non-overlapping occurrences: 6
'''
