Problem 1525

Abstract / Summary

Count how many ways a string can be split into two parts so each part has the same number of unique characters.

Note

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

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
21 lines | 517 bytes | submitted November 1, 2023 | GitHub   5% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

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
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 8 | μ = 7.19 | σ = 1.11

Complexity Analysis

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
generated automatically

Other Solutions

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
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++
27 links | 17 authors | 8 languages

Videos

6 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

6 solutions   November 1, 2023

Extra

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