Abstract / Summary

Split a string into two nonempty parts to maximize the sum of unique letters in each part.

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 65% (500k+ submissions).

Typical patterns to solve this problem:

• Prefix Sum
• 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 defines a Solution class with a single method maxScore. The method receives a binary string s and returns the maximum possible score obtainable by splitting the string into two non-empty substrings. The score for a particular split is defined as the number of '0' characters in the left part plus the number of '1' characters in the right part. The algorithm proceeds by scanning the string once, maintaining running counts of zeros on the left side and ones on the right side, and records the best combined total encountered.

Key Steps

The algorithm can be broken down into three logical phases, each illustrated with a focused code excerpt.

Initialisation of Counters Before the scan begins, two integer variables are prepared. left tracks the count of '0' characters that have been observed in the portion of the string that will become the left substring. right is seeded with the total number of '1' characters in the entire string, representing the count of ones that would belong to the right substring if the split were placed at the very beginning of the string.

left  = 0                     # count of zeros seen so far
right = s.count("1")          # total ones in the whole string

Iterative Update While Traversing the String The core loop iterates over every character except the final one (s[:-1]). This exclusion guarantees that both resulting substrings are non-empty. For each character, the algorithm updates the counters based on the character’s value: a '0' increments left, while a '1' decrements right because that one moves from the right side to the left side as the split point advances.

for c in s[:-1]:
    if c == "0":
        left += 1
    else:
        right -= 1

Recording the Best Score After adjusting the counters for the current split position, the algorithm computes the provisional score as the sum left + right. It then updates the running maximum result if this provisional score exceeds the previously recorded best.

    result = max(result, left + right)

When the loop finishes, result holds the highest achievable score across all valid split positions, and it is returned to the caller.

return result

Edge Cases Handled

The implementation gracefully manages several boundary conditions without requiring explicit checks.

When the input string consists entirely of '0' characters, the initial right count is zero. As the loop progresses, left grows while right remains unchanged, and the algorithm still evaluates each possible split, ultimately returning the count of zeros that can be placed on the left side (which is the length of the string minus one, because the right side must contain at least one character).

Conversely, if the string is composed solely of '1' characters, left never increments because no '0' appears. The right counter starts at the total length of the string and is decremented with each iteration, ensuring that the score reflects the decreasing number of ones on the right side as the split moves rightward. The algorithm still produces a valid maximum, which in this case is the total number of ones minus one.

The loop deliberately excludes the final character (s[:-1]). This design choice guarantees that the right substring is never empty, satisfying the problem’s requirement that both parts must contain at least one character. It also prevents an off-by-one error where the last character could be incorrectly counted as part of the left side without a corresponding right side.

If the input string has length two, the loop executes exactly once, evaluating the only permissible split. The counters are correctly updated for that single character, and the result reflects the correct score for the sole split configuration.

Performance Optimizations

The code exhibits several efficiency-focused decisions.

The total number of '1' characters is computed once using s.count("1"). By storing this value in right, the algorithm avoids repeated scanning of the string to determine the remaining ones after each split. This pre-computation reduces the overall work to a single pass plus a constant-time count operation.

The loop processes each character exactly once and updates simple integer variables. No auxiliary data structures (such as arrays or hash maps) are allocated during the traversal, keeping memory usage minimal.

The use of max inside the loop updates the best score in constant time. Because the provisional score is derived directly from the two counters, there is no need for additional calculations or temporary storage.

By iterating over s[:-1] rather than the full string and handling the split boundary implicitly, the algorithm eliminates the need for explicit boundary checks inside the loop body. This streamlines the control flow and reduces the number of conditional branches executed per iteration.

Overall, the solution achieves linear time performance relative to the length of the input string while maintaining a constant memory footprint, reflecting a well-optimized approach for the problem at hand.

Imagine you have a long row of building blocks, and some of them are zeros while others are ones. The goal is to slice this row into two separate piles at some point, and we want to arrange them so we collect the most points.

We look at the row and start by counting all the ones that are hiding in the pile on the right side. We also keep a little tally of the zeros that we find as we move along from the left.

As we walk past each block, we make a choice. If we find a zero, the left pile gets a little bit bigger. If we find a one, that means it is no longer in the right pile, so the right count gets a little bit smaller. After each step, we look at both piles and add their numbers together to see if this is the best score we have found so far. We keep checking every spot until we have gone almost all the way to the end, making sure to track the highest number of points we ever saw.

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	C++	Python		Java							TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java					Go	Rust	TS
	Progiez	C++	Python		Java
github	BigEggStudy							C#
	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim								C
	everthis			JS
	fartem					Ruby
	fsq	C++
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	pruthvikp		Python
	Shamik07						Dart
	varunu28				Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
pruthvikp	Python
Shamik07	Dart
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