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]

Examples

Example 1

Input

• devices = ["MotoG3", "GalaxyS5"]
• crashes = [(0,["A","B"]), (0,["A"]), (0,["C"]), (1,["B"]), (1,["C"])]
• k = 1

Output

• ["A", "B"]

Explanation MotoG3 has 3 crashes; GalaxyS5 has 2. Disabling A removes 2 MotoG3 crashes. Disabling B removes 1 crash on each device. Remaining crashes: MotoG3 has 1 (C), GalaxyS5 has 1 (C) → both meet k=1. No single flag can reduce both devices to ≤1.

Example 2

Input

• devices = ["Nexus5", "XperiaZ"]
• crashes = [(0,["X"]), (0,["Y"]), (1,["X","Y"])]
• k = 0

Output

• ["X", "Y"]

Explanation To reach zero crashes on both devices, you must prevent all events. Disabling only X leaves the Nexus5 Y crash; disabling only Y leaves the Nexus5 X crash.

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.