Abstract / Summary

Given a string and costs for each character, find the substring with the highest total cost.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 58% (50k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the maximum total “cost” of any contiguous substring of the input string s. Each character is assigned a numeric value: by default the letters 'a'-'z' receive values 1-26, and a separate mapping supplied by chars and vals can override those defaults. The algorithm then scans s once, applying a classic maximum-subarray (Kadane) technique to accumulate the best possible sum while discarding any prefix that would reduce the total.

Mapping characters to costs

The first phase builds a dictionary that translates every lower-case letter into its numeric contribution.

cost = {}
for i in range(26):                     # default values 1..26
    cost[chr(ord('a') + i)] = i + 1
for c, v in zip(chars, vals):           # override with special values
    cost[c] = v

The loop over the alphabet guarantees that every possible character in s has an entry, so later look-ups never raise a KeyError. The second loop replaces the default entry for any character that appears in chars, ensuring that the special values take precedence.

Edge handling in the mapping

If chars contains duplicate entries, the later occurrence in the zip iteration overwrites the earlier one, leaving the last supplied value as the effective cost. An empty chars list leaves the default mapping untouched, which is a valid scenario. Because the dictionary is built before processing s, the lookup cost during the main scan is O(1) per character.

Scanning the string with Kadane’s method

After the cost table is ready, the algorithm iterates through s, maintaining a running sum current.

current = 0
for c in s:
    current += cost[c]
    if current < 0:
        current = 0                     # discard negative prefix
    result = max(result, current)

At each step the character’s cost is added to current. If the accumulated sum becomes negative, it is reset to zero, effectively starting a new candidate substring after the current position. The variable result records the greatest sum observed so far.

Edge handling in the scan

When all characters have non-positive costs, the reset logic forces current back to zero each iteration, and result remains zero. Consequently the function returns zero for inputs where no positive-cost substring exists, which matches the conventional definition of the maximum subarray sum when empty subarrays are allowed. If the string is empty, the loop body never executes and the function returns the initial result value of zero, handling the empty-string edge case gracefully.

Performance optimizations

The code exhibits several deliberate choices that keep execution fast:

• The cost dictionary is populated once before the main loop, avoiding repeated conditional checks or recomputation of default values during the scan.
• Direct dictionary look-ups (cost[c]) provide constant-time access, eliminating the need for conditional branches that would arise from a series of if-elif statements.
• The Kadane loop uses only a few scalar variables (current, result) and updates them in place, minimizing memory allocation and keeping the CPU cache usage tight.
• Resetting current to zero instead of creating a new variable avoids extra object creation and leverages Python’s integer reuse for small values.

These choices together ensure that the algorithm runs in linear time relative to the length of s while using only a small, fixed amount of auxiliary space for the dictionary and a handful of integers.

Imagine you have a long train of colorful alphabet blocks. Each block has a number written on it, and some of those numbers are special because you decided what they should be. The goal is to find the longest stretch of blocks that gives you the highest total score possible.

First, you make a list that remembers what number belongs to every letter in the alphabet. Normally, the letter a is worth one, b is worth two, and so on until z, but if you have a special letter in your list, you change its value to whatever you want.

After you know the value of every letter, you walk along your train of blocks one by one. You keep a running total of the numbers you see. Every time you pick up a new block, you add its value to your total. If your total ever drops below zero, it means the blocks you are currently holding are making your score worse, so you drop them all and start fresh with a total of zero. As you walk, you always keep track of the biggest total score you have seen so far. By the time you reach the end of the train, that biggest score you saved is the answer.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java		C++		Python	TS
	WalkCCC	Java		C++		Python
	leetcode.ca	Java		C++	Go	Python	TS
	Progiez	Java		C++		Python
github	charles-wangkai	Java
	fsq			C++
	JoshCrozier		JS
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality