Your question is Group Anagrams and Max Subarray. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Coupa Spend Management receives supplier labels with inconsistent letter ordering and a chronological sequence of spend changes. Implement a function that groups labels that are anagrams and finds the largest sum of any non-empty contiguous range of spend changes.
Return a dictionary with anagram_groups and max_subarray_sum. Groups must appear in the order their signature is first encountered, and words within each group must preserve their input order. The spend result must be the maximum possible contiguous sum, even when every value is negative.
Input consists of labels, a list of lowercase strings, and changes, a non-empty list of integers. Return {"anagram_groups": groups, "max_subarray_sum": maximum_sum}.
Example 1:
Input: labels = ["care", "race", "acre", "coupa"], changes = [4, -1, 2, 1, -6, 3]
Output: {"anagram_groups": [["care", "race", "acre"], ["coupa"]], "max_subarray_sum": 6}
The first three labels share a letter signature. The best contiguous change range is [4, -1, 2, 1], whose sum is 6.
Example 2:
Input: labels = ["ab", "ba", "xy"], changes = [-8, -3, -5]
Output: {"anagram_groups": [["ab", "ba"], ["xy"]], "max_subarray_sum": -3}
When all changes are negative, the answer is the least negative single value.
def analyze_spend(labels, changes):