Show problems as
Classic problem #1781MediumHash TableStringCounting

Sum of Beauty of All Substrings

Real-world version: Total Spread Across Every Stretch of the Log
Tracked in this browser only
Read Sum of Beauty of All Substrings on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A machine shop writes its shift log as the string log, one lowercase letter per job, in the order the jobs ran.

A stretch is any run of consecutive letters of the log; a stretch is picked out by where it starts and where it ends, so two stretches at different places count separately even when they read the same. The spread of a stretch is how many times its busiest letter occurs in it, less how many times its quietest letter occurs in it, counting only letters that occur in that stretch at all.

Return the spreads of every stretch of log added together.

Examples

Example 1

Input
log = "ppqqp"
Output
4

Most stretches here even out to nothing. The stretch `"ppq"` contributes 1 and the whole log contributes 1, and the remaining contributions are similarly small.

Example 2

Input
log = "xyz"
Output
0

Every letter of this log is different, so no stretch has a busier letter than its quietest one.

Example 3

Input
log = "mmmnnm"
Output
9

The long run of `"m"` at the front leaves several stretches lopsided, and their contributions add up to the figure returned.

Constraints

  • 1 <= log.length <= 500
  • log consists of lowercase English letters only.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def total_spread(log: str) -> int:
Java
public int totalSpread(String log)

More on the same topics