FastPrepCount Legal Outfit Combinations

Count Legal Outfit Combinations

Duolingo logoDuolingo● MediumINTERNOA
Learn

Problem statement

You are given an array items of distinct clothing-item labels and an array illegalOutfits. Each row [a, b] in illegalOutfits identifies two different labels that may not appear together.

An outfit is a non-empty subset of items. An outfit is legal when it does not contain both labels from any forbidden pair. Repeated forbidden rows describe the same restriction.

Return the number of legal outfits as a signed 64-bit integer.

Function

countLegalOutfits(items: String[], illegalOutfits: String[][]) → long

Examples

Example 1

items = ["A","B","C"]illegalOutfits = [["A","B"],["A","C"]]return = 4

The legal non-empty subsets are [A], [B], [C], and [B, C]. Every other non-empty subset contains A together with B or C.

Example 2

items = ["hat","shirt","pants","shoes"]illegalOutfits = [["hat","shirt"],["pants","shoes"]]return = 8

For each forbidden pair, choose neither label or exactly one of its two labels. The two independent pairs therefore produce 3 * 3 = 9 subsets including the empty subset, so there are 8 legal outfits.

Constraints

  • 1 <= items.length <= 20.
  • Every value in items is a distinct non-empty string.
  • 0 <= illegalOutfits.length <= 100.
  • Every row in illegalOutfits contains exactly two distinct labels from items.
  • Repeated forbidden rows are allowed and represent the same restriction.
  • The answer fits in a signed 64-bit integer.

More Duolingo problems

See Duolingo hiring insights
public long countLegalOutfits(String[] items, String[][] illegalOutfits) {
    // Write your code here.
}
items["A","B","C"]
illegalOutfits[["A","B"],["A","C"]]
expected4
Checking account…