PracticeHashing

Repeated Document Snippets

EasyHashingtraversalfrequency countingstate tracking Time not estimated Not started

Context

A proofreading tool scans short token sequences extracted from documents. Identical sequences should share one record, even when they appear in different documents. You will count how often each distinct ordered sequence occurs, preserving the order in which distinct sequences first appear.

Problem

Given a collection of documents represented as lists of tokens, count the occurrences of every distinct document sequence. Two sequences are identical only when they have the same tokens in the same order. Return one frequency for each distinct sequence, ordered by that sequence's first appearance while scanning the outer collection from left to right and each document from left to right. An empty collection returns an empty list. Repeated sequences contribute to the same frequency, and an empty inner sequence is also a valid sequence.

Examples

Example 1

Input: documents = [["alpha", "beta"], ["gamma"], ["alpha", "beta"], ["gamma"]]

Output: [2, 2]

Explanation: The first example has two occurrences of ["alpha", "beta"] and two occurrences of ["gamma"], so its executed result is [2, 2].

Example 2

Input: documents = [["red"], ["red", "blue"], [], ["red"], ["red", "blue"], []]

Output: [2, 2, 2]

Explanation: The second example has two ["red"] sequences, two ["red", "blue"] sequences, and two empty sequences, so its executed result is [2, 2, 2].

Example 3

Input: documents = [["one", "two", "one"], ["two", "one"], ["one", "two", "one"], ["three"]]

Output: [2, 1, 1]

Explanation: The third example has two ["one", "two", "one"] sequences, one ["two", "one"] sequence, and one ["three"] sequence, so its executed result is [2, 1, 1].

Constraints

0 <= len(documents) <= 100
0 <= len(documents[i]) <= 20 for every i
1 <= len(documents[i][j]) <= 20 for every i, j
documents[i][j]: alphabet lowercase
documents tokens contain only lowercase letters.
Types: documents is str[][]; result is int[]

Function signature

def count_sequence_occurrences(documents: list[list[str]]) -> list[int]

documents list[list[str]]: A collection of token sequences extracted from documents.
returns list[int]: The frequencies of distinct sequences, listed in first-appearance order.

Adapted from MBPP problem task_779 (CC BY 4.0). Rewritten, extended and verified by Iksha.

Notes

The result order is determined by first appearance, not by alphabetical sorting.
An empty inner sequence is valid and must be counted like any other exact sequence.

Code

Saved

Checking environment…Python SandboxLn 1, Col 1

documents =