Code RoomLot stamp fuzzy matching
EasyPrep Room Coding #4839

Lot stamp fuzzy matching

CodingAlgorithms & data structuresEntry–Mid~14 min

A bottling line prints a lot stamp on every carton, and a camera reads the finished label reel back as one long line of characters. Ink smudges, so the checker still accepts a print that differs from the expected stamp in at most one character. Given scan and stamp, return every offset where stamp lines up against scan with at most one differing character, in ascending order. An offset counts when the stretch of scan beginning there is as long as stamp and disagrees with it in zero or one position. Overlapping offsets are all reported, so neighbouring offsets can both appear. Comparison is exact and case sensitive, since a lowercase letter marks a reprint. Return an empty list when stamp is empty, when stamp is longer than scan, or when nothing lines up.

Implement
single_smudge_offsets(scan: str, stamp: str) → list[int]
Examples
in["LOT7788A-MK","LOT7"]out[0]
in["kegs-3311-kegs-3312-kegs-3313","kegs-3312"]out[0,10,20]
in["banana","nn"]out[1,2,3,4]
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
["LOT7788A-MK","LOT7"][0]not run yetsample
["kegs-3311-kegs-3312-kegs-3313","kegs-3312"][0,10,20]not run yetsample
["banana","nn"][1,2,3,4]not run yetsample