How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

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.

Input: ("a", 0)

Expected Output: 0

Explanation: Length 1 string cannot be split into two non-empty substrings.

Input: ("aa", 0)

Expected Output: 1

Explanation: a|a shares {a}=1>0, which is valid.

Input: ("abab", 1)

Expected Output: 1

Explanation: Only ab|ab shares {a,b}=2>1. The a|bab and aba|b splits share only 1 char.

Input: ("aaaa", 0)

Expected Output: 3

Explanation: All 3 split points share {a}=1>0.

Input: ("abcdef", 0)

Expected Output: 0

Explanation: All characters are distinct; no character appears on both sides of any split, so shared count is always 0, never >0.

Hints

A partition shares a character c if and only if c appears in the prefix AND c appears in the suffix.
For each split point, you only need the SET of distinct characters on each side, not their counts.
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.

Input: ([5],)

Expected Output: 1

Explanation: Target 5: a single 1-item package.

Input: ([],)

Expected Output: 0

Explanation: No items, no packages.

Input: ([3, 3, 3],)

Expected Output: 3

Explanation: Target 3: three 1-item packages, beating target 6 (one pair).

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

Expected Output: 3

Explanation: Target 7: pairs (1,6),(2,5),(3,4) -> 3 packages.

Input: ([0, 0, 1, 1],)

Expected Output: 2

Explanation: Target 0: two 1-item packages from the zeros. Target 1 also gives two 1-item packages from the ones. Max is 2.

Input: ([1, 9, 2, 8, 5, 5],)

Expected Output: 3

Explanation: Target 10: pairs (1,9),(2,8),(5,5) -> 3 packages.

Hints

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.
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.
For 2-item packages with target S, greedily pair frequency[a] with frequency[S-a]; handle a == S-a (same value) using count//2.

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.