URL Segment Compression Part 3 — Global Token Budget
Stripe● MediumNEW GRADONSITE INTERVIEWProblem statement
Continue the URL compression sequence. A path has major parts separated by / and minor parts separated by .. Base-compress a word by keeping its first and last character and replacing the middle with the number of omitted characters.
Each major may contain at most m output tokens, and the complete path may contain at most t output tokens. Every major must retain at least one token.
For this practice version, assign one token to every major first. Give the remaining global token budget to major parts from left to right, never exceeding m or that major's original minor-part count. Within a major with budget q, compress its first q-1 minor parts separately, concatenate all remaining original minor parts, and compress that concatenation as its final token.
The merge always uses original characters, not already-compressed text.
Practice sequence
- Part 1: compress every minor part
- Part 2: cap each major separately
- Part 3: enforce a global token budget (current)
Function
compressGlobal(s: String, m: int, t: int) → StringExamples
Example 1
s = "alpha.beta.gamma/delta.echo.foxtrot/golf.hotel.india"m = 2t = 5return = "a3a.b7a/d3a.e9t/g12a"One token is reserved per major. The two remaining tokens go to the first and second majors, so their budgets are [2,2,1].
Example 2
s = "stripe.com/payments/checkout/customer.john.doe"m = 2t = 4return = "s7m/p6s/c6t/c13e"There are four majors and four global tokens, so every major receives one token and merges all of its original minor parts.
Constraints
1 <= m.- Let
kbe the number of major parts.k <= t <=the sum of allmin(m, minorCount)values. - The input has no empty major or minor parts.
- Every minor part has length at least
2. - The middle count may contain multiple digits.