Design Prefix-Aware Deduplication for Homepage Content Rows

Problem Statement

On the Netflix homepage, content is arranged in horizontal rows (e.g., "Trending Now", "Top 10"). To maintain visual diversity above the fold, the platform enforces a prefix deduplication policy:

1. Protected Prefix: For a non-exempt row i, the first prefix_limits[i] items added to the row must not appear in the protected prefix of any previously constructed non-exempt row.
2. Suffix / Beyond Prefix: Once a row's protected prefix reaches prefix_limits[i] items, subsequent items added to that row only need to be unique within that specific row (they may duplicate items from other rows' prefixes or suffixes).
3. Within-Row Uniqueness: No row may contain the same title more than once, regardless of prefix or suffix position.
4. Exempt Rows: Rows marked as exempt (e.g., "Continue Watching" or "My List") do not participate in cross-row prefix deduplication: they do not check against previously used prefix items, nor do their items block subsequent rows' prefixes.
5. Shortfall: If a row's candidate list runs out of eligible titles before reaching its target length target_lengths[i], output all valid titles gathered without error.

Implement the function deduplicate_homepage_rows that processes rows in order and returns the filtered rows.

Function Signature

def deduplicate_homepage_rows(
    candidate_rows: list[list[str]],
    prefix_limits: list[int],
    target_lengths: list[int],
    exempt_row_indices: set[int] | None = None,
) -> list[list[str]]:
    pass

Input & Constraints

• candidate_rows: A list of R lists, where each list contains string identifiers representing candidate titles in priority order. 0 <= R <= 1000.
• prefix_limits: A list of R non-negative integers (0 <= prefix_limits[i] <= target_lengths[i]).
• target_lengths: A list of R non-negative integers (0 <= target_lengths[i] <= 500).
• exempt_row_indices: An optional set of row indices 0 <= idx < R indicating exempt rows.
• Total number of candidate strings across all rows <= 200,000.

Examples

Example 1

candidate_rows = [
    ["A", "B", "C", "D"],
    ["B", "A", "E", "B", "C"],
]
prefix_limits = [2, 2]
target_lengths = [3, 3]
exempt_row_indices = set()

# Output:
# [
#   ["A", "B", "C"],
#   ["E", "B", "C"]
# ]

Explanation:

• Row 0: Takes "A" and "B" as prefix items. Global prefix set is now {"A", "B"}. Suffix takes "C". Row 0 target (3) reached.
• Row 1: Candidate "B" is rejected from prefix because it is in global prefix set. Candidate "A" is also rejected. Candidate "E" fills prefix slot 1. Candidates run out of new prefix items? Wait, the next candidate is "B" (still rejected for prefix) and "C" (not in prefix set, fills prefix slot 2). Wait, in candidate list: ["B", "A", "E", "B", "C"]:
  • "B" rejected for prefix (in global prefix set).
  • "A" rejected for prefix (in global prefix set).
  • "E" accepted as prefix item 1 (global prefix set now {"A", "B", "E"}).
  • Next is "B" (rejected for prefix).
  • "C" accepted as prefix item 2 (global prefix set now {"A", "B", "E", "C"}).
  • Prefix filled (size 2). Next candidate for suffix: list exhausted. Result for Row 1 is ["E", "C"].

Example 2 (With Suffix Duplication & Exempt Row)

candidate_rows = [
    ["X", "Y", "Z"],
    ["X", "W", "V"],
]
prefix_limits = [1, 1]
target_lengths = [2, 2]
exempt_row_indices = {1}

# Output:
# [
#   ["X", "Y"],
#   ["X", "W"]
# ]

Explanation: Row 1 is exempt, so "X" can be used as its prefix title even though Row 0 already used "X" in its prefix.