#1525

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Good Ways to Split a String

Count all valid splits of a string where left and right substrings have equal distinct characters, using efficient state transitions.

hash table string dynamic programming bit manipulation

Problem Statement

Given a string s, you can split it into two non-empty parts sleft and sright at any index. A split is considered good if the number of unique letters in sleft equals the number of unique letters in sright. Your task is to determine how many such good splits exist for the input string s.

For example, given s = "aacaba", there are multiple ways to split, but only the splits ("aac", "aba") and ("aaca", "ba") have equal distinct letters on both sides. Return the total count of these good splits. Constraints: 1 <= s.length <= 10^5 and s contains only lowercase English letters.

Examples

Example 1

Input: s = "aacaba"

Output: 2

There are 5 ways to split "aacaba" and 2 of them are good. ("a", "acaba") Left string and right string contains 1 and 3 different letters respectively. ("aa", "caba") Left string and right string contains 1 and 3 different letters respectively. ("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split). ("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split). ("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.

Example 2

Input: s = "abcd"

Output: 1

Split the string as follows ("ab", "cd").

Constraints

1 <= s.length <= 105
s consists of only lowercase English letters.

Solution Approach

Use Two Hash Maps to Track Counts

Initialize two hash maps: leftCount and rightCount. Populate rightCount with the frequency of all characters. Iterate through s, moving one character at a time from rightCount to leftCount, updating counts. If the number of keys in leftCount equals keys in rightCount, increment the result. This leverages the state transition dynamic programming pattern by maintaining valid character states efficiently.

Optimize with Single Pass

Instead of recomputing distinct counts at every split, update counts incrementally for each index. Removing characters from rightCount and adding to leftCount at each step ensures O(n) time. This prevents repeated scanning of substrings and avoids the main failure mode of naive solutions that try to count distinct letters from scratch for every possible split.

Consider Edge Cases

Handle minimal strings (length 1) where no split is possible. Ensure updates of counts remove entries when frequency reaches zero to keep key counts accurate. This avoids off-by-one errors in dynamic state tracking, which is the main pitfall in this problem's state transition approach.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each character is moved once between leftCount and rightCount. Space complexity is O(1) in practice, as there are at most 26 lowercase letters stored in the hash maps.

What Interviewers Usually Probe

Checking if the candidate updates counts efficiently rather than recomputing distinct letters from scratch.
Observing whether the candidate recognizes the problem as a state transition DP pattern with hash maps.
Looking for handling of edge cases where strings are too short for any valid split.

Common Pitfalls or Variants

Common pitfalls

Recomputing distinct characters for every split, causing O(n^2) time and timeout on large inputs.
Forgetting to remove letters from rightCount when their count reaches zero, which inflates the distinct count incorrectly.
Ignoring edge cases with minimal string length or repeated characters leading to wrong good split count.

Follow-up variants

Count good splits when ignoring case sensitivity for letters.
Return all the indices where good splits occur instead of just the count.
Allow Unicode characters, requiring more generic hash maps for character tracking.

FAQ

What defines a good split in this problem?

A split of s into sleft and sright is good if both sides contain the same number of distinct letters.

Can this be solved without hash maps?

Using arrays for fixed lowercase letters is possible, but hash maps generalize better for dynamic state transition tracking.

What is the key pattern used in this problem?

The problem uses a state transition dynamic programming pattern to maintain and compare distinct letter counts efficiently.

How to handle very long strings efficiently?

Incrementally update leftCount and rightCount while iterating to ensure O(n) time instead of recomputing distinct letters repeatedly.

What common mistakes should I avoid?

Avoid recomputing distinct counts at every split and remember to remove characters from the right hash map when their count reaches zero.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def numSplits(self, s: str) -> int:
        cnt = Counter(s)
        vis = set()
        ans = 0
        for c in s:
            vis.add(c)
            cnt[c] -= 1
            if cnt[c] == 0:
                cnt.pop(c)
            ans += len(vis) == len(cnt)
        return ans

Continue Practicing

#691 stickers to spell word #1371 find the longest substring containing vowels in even counts #1684 count the number of consistent strings