Find motif in packed signal
A capture card stores a long signal packed as runs to save space. run_chars[i] holds the character of run i and run_lengths[i] holds how many times it repeats, so the signal is every run written out in order. Neighbouring runs never carry the same character, every run length is at least 1, and a single run can be a billion characters long, so writing the signal out in full is not an option. Given the packed runs and a short motif, return how many times motif occurs in the signal. Occurrences may overlap, so aa occurs 4 times inside a run of 5 a characters. Return 0 when motif is empty, when there are no runs, or when motif is too long to fit.
packed_run_hit_count(run_chars: list[str], run_lengths: list[int], motif: str) → int[["a","b","a"],[5,1,2],"aa"]out5[["a","b"],[3,4],"aab"]out1[["x"],[1000000000],"xx"]out999999999State 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.
[["a","b","a"],[5,1,2],"aa"]5not run yetsample[["a","b"],[3,4],"aab"]1not run yetsample[["x"],[1000000000],"xx"]999999999not run yetsample