Split Prefix Suffix
Updated
Problem statement
Amazon Prime Day is a day where many items are put on sale for Amazon Prime members. A list of sale items is assembled where each item is assigned a category denoted by a lowercase English letter.
Since the sale is to be held on two different days, the company has decided to split the list of items into two contiguous non-empty sub-lists - a prefix and a suffix. To ensure that both days share a sufficient number of similar items, they also need to split it in a way such that the number of distinct categories shared by both sub-lists is greater than k.
Formally, given a string, categories, find the number of ways to split the string into exactly two contiguous non-empty substrings such that the number of distinct characters occurring in both the substrings is greater than a given integer k.
Function
splitPrefixSuffix(categories: String, k: int) → int
Complete the function splitPrefixSuffix in the editor.
splitPrefixSuffix has the following parameters:
string categories: the categoriesint k: shared distinct categories must be greater than this value
Returns
int: the number of ways to split the given string
Examples
Example 1
categories = "abbcac"k = 1return = 2
Constraints
1 ≤ length(categories) ≤ 10^50 ≤ k ≤ 26- The string
categoriesconsists of lowercase English characters.
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Shortest Digit Prefix for Target MultisetsVisa · OAVisa interview questions
- Longest Balanced Substring After One SwapTekion · OATekion interview questions
- Longest Substring with Even OccurrencesDeloitte · OADeloitte interview questions
- Extraordinary SubstringsPalantir · OAPalantir interview questions
- Number of Divisible Substrings (For MLE)Wayfair · OAWayfair interview questions
- Longest Equal-Frequency SubstringDRW · PHONE SCREENDRW interview questions
- Weighted Next-Word Prediction From Training SequencesGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Subscription and Usage-Based Billing CalculatorStripe · OAStripe interview questions
- Earliest Time to Schedule a MeetingMathWorks · OAMathWorks interview questions
- Count Subarrays with a Perfect-Square ProductMicrosoft · OAMicrosoft interview questions