Code RoomDocument shingle count
EasyPrep Room Coding #4789

Document shingle count

CodingAlgorithms & data structuresEntry–Mid~14 min

A help centre deduplicator measures how alike two articles are by cutting each one into shingles. A shingle is a run of exactly width consecutive characters, taken at every starting position, so neighbouring runs overlap in all but one character. A run holding a space is not a shingle, because the tool never lets one straddle a word break, and that run is dropped. Given document and width, return how many distinct shingles the document yields. A shingle that turns up in ten places still counts once, and shingles are compared exactly, so case matters. Return 0 when width is zero or negative, and 0 when width is longer than the document, since no run that size exists. This count is the denominator the tool divides shared shingles by.

Implement
unique_shingle_count(document: str, width: int) → int
Examples
in["banana",3]out3
in["hot pot",3]out2
in["aaaa",2]out1
What a strong answer looks like

State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.

0:00 of about 14 min
InputExpectedGot
["banana",3]3not run yetsample
["hot pot",3]2not run yetsample
["aaaa",2]1not run yetsample