Minimize Legacy Device Crash Rate

Problem Narrative

You’re on-call for a fintech app with 8M DAUs. A new release is stable on modern phones, but older Android devices (API 21–23) are crashing at a rate that risks a payment-flow rollback. Your mobile team can remotely disable specific feature flags (e.g., “animated charts”, “new crypto quote stream”), and crash reports show which flags were enabled when each crash occurred.

You need an algorithm to quickly decide which flags to disable so that every legacy device model falls below a crash threshold, while minimizing the number of flags you turn off (to reduce revenue impact).

Formal Task

You are given:

• devices: a list of device model names.
• crashes: a list of crash events, each event is a tuple (device_index, enabled_flags) where:
  • device_index is an integer index into devices.
  • enabled_flags is a list of strings representing flags enabled during that crash.
• An integer k (maximum allowed crashes per device after mitigation).

If you disable a flag, then all crash events that include that flag are prevented (removed) across all devices.

Return a list of disabled flags (strings) with minimum length such that, after removing all prevented crashes, each device has at most k remaining crashes. If multiple optimal answers exist, return the one that is lexicographically smallest when sorted.

Function Signature

def minimize_disabled_flags(devices: list[str], crashes: list[tuple[int, list[str]]], k: int) -> list[str]

Constraints

• 1 <= len(devices) <= 200
• 0 <= len(crashes) <= 5000
• 0 <= k <= len(crashes)
• Each enabled_flags list has 1..10 flags
• Flag names are lowercase/uppercase ASCII strings, length 1..20

Notes

• A crash event is prevented if any of its enabled flags is disabled.
• If the current crash counts already satisfy the threshold, return an empty list.