FastPrep
Problem · String

Maximum Equal Parts for Prefixes

Learn this problem
● MediumAmazon logoAmazonINTERNOA
See Amazon hiring insights

Problem statement

A team at Amazon is working to ensure all packages are correctly sorted for delivery. Each package has a label represented by an uppercase English letter. The full list of labels is given as the string packages, where the ith character is the label of the ith package.

To optimize the sorting process, the team wants to analyze each prefix of the string packages (from length 1 to n) and determine the maximum number of equal parts it can be divided into. Each part must satisfy the following conditions:

  • Each part must have the same frequency of every character as every other part in that division

Given a string packages, calculate for each prefix t (from length 1 to n), the maximum number of equal parts into which the prefix can be divided, such that each part has the same number of occurrences of each character.

Function

maximumEqualParts(packages: String) → int[]

Examples

Example 1

packages = "ABAB"return = [1, 1, 1, 2]
Example 1 illustration

Given, packages = "ABAB".

In the given example t represents prefix string and length represents the length of the prefix string.

Return [1, 1, 1, 2] as the answer.

Constraints

  • packages consists only of uppercase English letters ('A' to 'Z').
  • The answer is computed for every prefix of packages of length 1 to n, where n is the length of packages.
  • For each prefix, the maximum number of equal parts is at least 1, since a prefix can always be treated as a single undivided part.

More Amazon problems

drafts saved locally
public int[] maximumEqualParts(String packages) {
  // write your code here
}
packages"ABAB"
expected[1, 1, 1, 2]
checking account