Python 1525.py
class Solution:
def numSplits(self, s: str) -> int:
result = 0
total = defaultdict(int)
for c in s:
total[c] += 1
have = set()
for c in s:
have.add(c)
total[c] -= 1
if total[c] == 0:
del total[c]
if len(have) > len(total): # not needed, just makes it faster
break
if len(have) == len(total):
result += 1
return result
Difficulty
and has an acceptance rate of about 69% (100k+ submissions).
Typical patterns to solve this problem:
- Bit Manipulation
- Dynamic Programming
- Hash Table
- Prefix Sum
- String
AI Disclaimer
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.
Code Walkthrough
Overview
The numSplits method computes how many positions in a given string s can be used to split the string into two non-empty parts such that the set of distinct characters on the left side has the same size as the set of distinct characters on the right side. The algorithm walks through the string once, maintaining a running view of characters seen so far and characters that remain to the right.
Key Steps
Constructing the right-side frequency map
Before the main scan, the code builds a frequency dictionary that records how many times each character appears in the whole string. This map represents the characters that are still available on the right side of any potential split.
total = defaultdict(int)
for c in s:
total[c] += 1
Updating left-side set and right-side map while scanning
The algorithm iterates over the characters of s from left to right. For each character it adds the character to a set have, which tracks distinct characters that have appeared on the left side. Simultaneously it decrements the count in total; when a count drops to zero the entry is removed, keeping the map size equal to the number of distinct characters still unseen on the right.
have = set()
for c in s:
have.add(c)
total[c] -= 1
if total[c] == 0:
del total[c]
Early termination when left side cannot be matched
An optimization checks whether the left side already has more distinct characters than the right side. If this condition becomes true, no later split can satisfy equality, so the loop exits early.
if len(have) > len(total): # not needed, just makes it faster
break
Counting positions where the distinct counts match
When the size of the left-side set equals the size of the right-side map, a valid split point is found and the result counter is incremented.
if len(have) == len(total):
result += 1
Finally, the method returns the accumulated count.
return result
Edge Cases Handled
When the input string is empty, the initial frequency map is empty and the loop body never executes, leaving result at zero, which correctly reflects that no split is possible.
If the string consists of a single repeated character, the left-side set will contain one element after the first iteration, while the right-side map becomes empty after the same character’s count is exhausted. The early-termination condition (len(have) > len(total)) triggers, preventing unnecessary further iterations.
For strings where all characters are distinct, the left-side set grows one by one, and the right-side map shrinks correspondingly. The equality check will be true exactly at the midpoint when the number of distinct characters on each side matches, and the algorithm correctly counts that split.
When the string contains a mixture of repeated and unique characters, the removal of entries from total as their counts reach zero ensures that len(total) always reflects the current number of distinct characters still to the right, allowing accurate comparison with len(have) at each step.
Performance Optimizations
The use of defaultdict(int) provides O(1) amortized updates for the frequency map without needing explicit existence checks.
Maintaining a set for the left side gives constant-time membership and size queries, enabling quick determination of distinct character count on the left.
Deleting entries from total as soon as their count drops to zero keeps the dictionary’s size minimal, which reduces the cost of subsequent len(total) evaluations.
The early-exit condition (len(have) > len(total)) prevents the algorithm from scanning the remainder of the string once it becomes impossible for the distinct counts to match, saving work especially on long strings with many repeated characters.
Overall, the method processes the string in a single pass with lightweight data structures, achieving efficient execution for typical input sizes.
ELI5 - Simplified Explanation
Imagine a long row of colorful building blocks that make up a word. The goal is to find how many ways to split this row into two separate piles so that each pile has the exact same number of unique colored blocks.
First, a special bag is filled with all the blocks in the row to count how many of each color are present. This helps keep track of everything available.
Next, the row of blocks is walked through one by one from the left. As each block is picked up, it is put into a new pile on the left side, and one is removed from the special bag representing the right side.
After each block is moved, the number of different colored blocks in the left pile is checked against the number of unique colors remaining in the bag for the right pile. If those two counts are equal, it means a perfect split has been found, so a point is added to the total score.
This continues until all blocks have been inspected, which finds every single spot where the row can be split to make both sides share the same variety of colors.
Code Quality
Complexity Analysis
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
Other Solutions
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 | |||||
| Progiez | C++ | Python | Java | ||||||
| github | black-shadows | C++ | |||||||
| charles-wangkai | Java | ||||||||
| everthis | JS | ||||||||
| fartem | Ruby | ||||||||
| FelixFan1122 | Java | ||||||||
| fsq | C++ | ||||||||
| haoel | C++ | ||||||||
| JoshCrozier | JS | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python | ||||||||
| wisdompeak | C++ | ||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||
| WalkCCC | C++, Python, Java | ||||||||
| leetcode.ca | C++, Go, Java, Python | ||||||||
| Progiez | C++, Java, Python | ||||||||
| black-shadows | C++, C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JavaScript | ||||||||
| fartem | Ruby | ||||||||
| FelixFan1122 | Java | ||||||||
| fsq | C++ | ||||||||
| haoel | C++ | ||||||||
| JoshCrozier | JavaScript | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python | ||||||||
| wisdompeak | C++ |
Videos
Solved On The Same Day
- problem 897: Increasing Order Search Tree
- problem 1534: Count Good Triplets
- problem 1222: Queens That Can Attack the King
- problem 1418: Display Table of Food Orders in a Restaurant
- problem 2265: Count Nodes Equal to Average of Subtree
Extra
- 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