Number of Good Ways to Split a String — Medium Problem & Solution

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.

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 <= 100000
s consists of lowercase English letters.

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 i from n-1 down to 0, inserting s[i] into a counting array and recording right[i] — the number of distinct letters in s[i..n-1].
Walk i from 0 to n-2, inserting s[i] into a second counting array and tracking leftDistinct.
The cut after index i is good when leftDistinct == 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue