Quick Overview

This question evaluates string-processing and combinatorial counting skills, including tracking distinct-character occurrences across contiguous partitions and using frequency-based pairing logic on arrays to form equal-cost packages.

Count partitions and equal-cost packages

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

##### Question Given a string itemCategories, count the number of ways to partition it into exactly two contiguous non-empty substrings (a prefix and a suffix) such that the number of distinct characters appearing in both substrings is greater than k. Given an array itemCosts representing item costs, determine the maximum number of packages that can be created so that each package contains at most two items, all packages have the same total cost, and each item is used in at most one package.

Quick Answer: This question evaluates string-processing and combinatorial counting skills, including tracking distinct-character occurrences across contiguous partitions and using frequency-based pairing logic on arrays to form equal-cost packages.

Count Valid Prefix/Suffix Partitions

Given a string `itemCategories` and an integer `k`, count the number of ways to partition the string into exactly two contiguous non-empty substrings (a prefix and a suffix) such that the number of DISTINCT characters that appear in BOTH the prefix and the suffix is strictly greater than `k`. A partition is made by choosing a split point `i` (1 <= i <= n-1); the prefix is `itemCategories[0..i-1]` and the suffix is `itemCategories[i..n-1]`. A partition is valid if `|distinct(prefix) ∩ distinct(suffix)| > k`. Return the count of valid partitions. Example: `itemCategories = "aabba"`, `k = 1`. The only valid split is `"aab" | "ba"`, where both sides share distinct characters {a, b} (2 > 1). Answer: 1.

Constraints

  • 1 <= len(itemCategories) <= 10^5
  • itemCategories consists of lowercase/uppercase letters (or any characters)
  • 0 <= k <= 26 (or up to the alphabet size)

Examples

Input: ("aabba", 1)

Expected Output: 1

Explanation: Splits: a|abba (share {a}=1), aa|bba (share {a}=1), aab|ba (share {a,b}=2>1 VALID), aabb|a (share {a}=1). Only 1 valid.

Input: ("abcabc", 2)

Expected Output: 1

Explanation: Only abc|abc shares all 3 distinct chars {a,b,c}=3>2. Other splits share at most 2.

Hints

  1. A partition shares a character c if and only if c appears in the prefix AND c appears in the suffix.
  2. For each split point, you only need the SET of distinct characters on each side, not their counts.
  3. To optimize beyond O(n^2): precompute, for each character, the first and last index it appears at. A character is shared by the split at i iff its first occurrence is < i and its last occurrence is >= i.

Maximum Equal-Cost Packages

Given an array `itemCosts` of integers representing item costs, determine the maximum number of packages that can be created such that: 1. Each package contains AT MOST two items (so one or two items). 2. ALL packages have the same total cost. 3. Each item is used in at most one package (items cannot be reused). You may choose any target total cost. Return the maximum number of packages achievable. Example: `itemCosts = [1, 2, 3, 4]`. Choosing target cost 5, you can form packages (1,4) and (2,3) — 2 packages. No choice yields more. Answer: 2.

Constraints

  • 0 <= len(itemCosts) <= 10^4
  • 0 <= itemCosts[i] <= 10^9
  • A package may contain one item (cost == target) or two items (costs sum to target)

Examples

Input: ([1, 2, 3, 4],)

Expected Output: 2

Explanation: Target 5: pairs (1,4) and (2,3) -> 2 packages, the maximum.

Input: ([2, 2, 2, 2],)

Expected Output: 4

Explanation: Target 2: four 1-item packages (each item costs 2). Better than target 4 which only yields 2 pair-packages.

Hints

  1. The target total cost must be either a single item's cost (1-item package) or the sum of two item costs (2-item package), so only those values are worth trying.
  2. To MAXIMIZE the number of packages for a fixed target, prefer 1-item packages (use an item whose cost equals the target) before pairing, since a package counts the same whether it holds 1 or 2 items but a single uses fewer items.
  3. For 2-item packages with target S, greedily pair frequency[a] with frequency[S-a]; handle a == S-a (same value) using count//2.

Loading coding console...