Number of Good Ways to Split a String — Problem & Solution
Number of Good Ways to Split a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Number of Good Ways to Split a String is a medium coding problem on strings, hash table and prefix sum, asked in Amazon, Google and Zomato interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Prefix Sum
- Asked at: Amazon, Google, Zomato
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A split of s into two non-empty parts sLeft + sRight is good when the number of distinct letters in sLeft equals the number of distinct letters in sRight.
Return how many good splits exist.
Example 1
Input: s = "aacaba"
Output: 2
Explanation: Splitting after index 1 gives ("aa","caba") — 1 vs 3. The good splits are after index 2 and after index 3.
Example 2
Input: s = "abcd"
Output: 1
Explanation: Only ("ab","cd") balances at 2 and 2.
Example 3
Input: s = "aaaaa"
Output: 4
Explanation: Every split gives 1 distinct letter on each side.
Constraints
2 <= s.length <= 100000s consists of lowercase English letters.
Hints for Number of Good Ways to Split a String
Hint 1
For each cut position you need two numbers: distinct on the left and distinct on the right.
Hint 2
One right-to-left pass can precompute the suffix distinct count at every index.
Hint 3
Then a left-to-right pass grows the prefix set and compares.
How to solve Number of Good Ways to Split a String
Precompute the suffix distinct count for every index in one backward pass, then sweep forward maintaining the prefix distinct count and compare at each cut.
Approach
- Walk
ifromn-1down to0, insertings[i]into a counting array and recordingright[i]— the number of distinct letters ins[i..n-1]. - Walk
ifrom0ton-2, insertings[i]into a second counting array and trackingleftDistinct. - The cut after index
iis good whenleftDistinct == right[i + 1]; count those.
Why it works
right[i+1] is exactly the distinct count of the suffix that begins right after the cut, and leftDistinct after inserting s[i] is exactly the distinct count of the prefix through i — the two quantities the definition compares. Stopping at n-2 keeps both parts non-empty.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Cutting after the last character leaves an empty right part, which is not allowed.
- Recomputing the suffix distinct count inside the forward loop turns a linear solution quadratic.
- Using a set of characters rather than counts makes the backward pass harder to get right — a counting array with a 'first sighting' test is simpler.
Reference solution
Python
def numSplits(s: str) -> int:
n = len(s)
right = [0] * n
count = [0] * 26
distinct = 0
for i in range(n - 1, -1, -1):
c = ord(s[i]) - 97
if count[c] == 0:
distinct += 1
count[c] += 1
right[i] = distinct
seen = [0] * 26
left_distinct = 0
total = 0
for i in range(n - 1):
c = ord(s[i]) - 97
if seen[c] == 0:
left_distinct += 1
seen[c] += 1
if left_distinct == right[i + 1]:
total += 1
return totalJava
public static int numSplits(String s) {
int n = s.length();
int[] right = new int[n];
int[] count = new int[26];
int distinct = 0;
for (int i = n - 1; i >= 0; i--) {
int c = s.charAt(i) - 'a';
if (count[c] == 0) distinct++;
count[c]++;
right[i] = distinct;
}
int[] seen = new int[26];
int leftDistinct = 0, total = 0;
for (int i = 0; i + 1 < n; i++) {
int c = s.charAt(i) - 'a';
if (seen[c] == 0) leftDistinct++;
seen[c]++;
if (leftDistinct == right[i + 1]) total++;
}
return total;
}C++
int numSplits(string s) {
int n = (int) s.size();
vector<int> right(n, 0), count(26, 0);
int distinct = 0;
for (int i = n - 1; i >= 0; i--) {
int c = s[i] - 'a';
if (count[c] == 0) distinct++;
count[c]++;
right[i] = distinct;
}
vector<int> seen(26, 0);
int leftDistinct = 0, total = 0;
for (int i = 0; i + 1 < n; i++) {
int c = s[i] - 'a';
if (seen[c] == 0) leftDistinct++;
seen[c]++;
if (leftDistinct == right[i + 1]) total++;
}
return total;
}JavaScript
var numSplits = function(s) {
var n = s.length;
var right = [], count = [];
for (var t = 0; t < n; t++) right.push(0);
for (var u = 0; u < 26; u++) count.push(0);
var distinct = 0;
for (var i = n - 1; i >= 0; i--) {
var c = s.charCodeAt(i) - 97;
if (count[c] === 0) distinct++;
count[c]++;
right[i] = distinct;
}
var seen = [];
for (var v = 0; v < 26; v++) seen.push(0);
var leftDistinct = 0, total = 0;
for (var j = 0; j + 1 < n; j++) {
var d = s.charCodeAt(j) - 97;
if (seen[d] === 0) leftDistinct++;
seen[d]++;
if (leftDistinct === right[j + 1]) total++;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets