Code RoomRegister motif under renaming
HardPrep Room Coding #4886

Register motif under renaming

CodingAlgorithms & data structuresMid–Staff~35 min

A compiler pass writes a trace where each step is named by the register it wrote, one lowercase letter per step. A clone detector hunts for a motif that turns up again under a consistent renaming of registers, since the shape of the reuse matters and the names do not. A window of the trace matches the motif when there is a one to one pairing between the letters of the motif and the letters of the window that turns one into the other, so the same motif letter always pairs with the same window letter and two motif letters never share a window letter. The motif ab therefore matches xy and yx but never zz. Given trace and motif, return the start index of every window that matches, ascending. Windows may overlap. Return an empty list when the motif is empty or longer than the trace.

Implement
renamed_clone_starts(trace: str, motif: str) → list[int]
Examples
in["abcabd","xyzxy"]out[0]
in["aaab","xy"]out[2]
in["mnmn","pq"]out[0,1,2]
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 35 min
InputExpectedGot
["abcabd","xyzxy"][0]not run yetsample
["aaab","xy"][2]not run yetsample
["mnmn","pq"][0,1,2]not run yetsample