Number of Good Ways to Split a String

Medium
651.

Number of Good Ways to Split a String

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.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var numSplits = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Number of Good Ways to Split a String

  1. Hint 1

    For each cut position you need two numbers: distinct on the left and distinct on the right.

  2. Hint 2

    One right-to-left pass can precompute the suffix distinct count at every index.

  3. 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

  1. 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].
  2. Walk i from 0 to n-2, inserting s[i] into a second counting array and tracking leftDistinct.
  3. 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

Java

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