Problem Description

The Leetcode problem Number of Good Ways to Split a String asks you to determine how many ways you can split a given string s (consisting of only lowercase English letters) into two non-empty parts, such that the number of distinct letters in the left part is equal to the number of distinct letters in the right part.

More formally, you need to count the number of indices i (where 1 ≤ i < s.length) such that the substring s[0:i] and s[i:] each contain the same number of unique characters.

• Each split must be between two characters (not at the ends).
• You cannot reuse characters across the split; each side is considered separately.
• The input string can be up to 10⁵ characters long.

Thought Process

At first glance, the problem suggests checking every possible split of the string and comparing the number of unique characters on both sides. This brute-force approach would involve, for each split point, creating two substrings and counting their unique letters using, for example, a set. However, this would be too slow for large strings since both substring creation and set operations are costly.

To optimize, we need to avoid recalculating the number of unique characters for each split. Instead, we can precompute or incrementally track the number of unique characters as we move the split point from left to right. This way, we can solve the problem efficiently in a single or double pass.

Solution Approach

We can solve the problem efficiently using two passes and some auxiliary data structures:

1. First Pass (Right to Left):
   • We create an array right_unique where right_unique[i] stores the number of unique characters in the substring s[i:].
   • We use a set or a frequency array to keep track of unique characters as we traverse from the end of the string to the beginning.
2. Second Pass (Left to Right):
   • We use another set or frequency array to track unique characters in the left part (s[0:i]).
   • At each possible split point i, we compare the count of unique characters on the left (from our tracking structure) with right_unique[i].
   • If they are equal, we increment our answer counter.

By maintaining counts incrementally, we avoid redundant work and solve the problem in linear time.

Example Walkthrough

Let's walk through the process with the example s = "aacaba":

1. Right to Left Pass:
   • Start from the end and move left, adding each character to a set and recording the size at each position:
   • Positions (from right):
     a (unique: 1), b (unique: 2), a (unique: 2), c (unique: 3), a (unique: 3), a (unique: 3)
   • This gives us right_unique = [3, 3, 3, 2, 1, 0] (last 0 is unused).
2. Left to Right Pass:
   • Start from the beginning, add each character to a set, and at each split point i, compare the size of the set (left unique count) with right_unique[i]:
   • • i = 1: left = "a" (unique: 1), right = "acaba" (unique: 3) → not equal
     • i = 2: left = "aa" (unique: 1), right = "caba" (unique: 3) → not equal
     • i = 3: left = "aac" (unique: 2), right = "aba" (unique: 2) → equal → count = 1
     • i = 4: left = "aaca" (unique: 2), right = "ba" (unique: 2) → equal → count = 2
     • i = 5: left = "aacab" (unique: 3), right = "a" (unique: 1) → not equal
   • So, the answer is 2.

Time and Space Complexity

• Brute-force Approach:
  • For each split, create two substrings and count unique letters using a set.
  • Time Complexity: O(N²), since for each of N splits, counting unique letters takes up to O(N).
  • Space Complexity: O(N) for sets per split.
• Optimized Approach (as described above):
  • Two passes through the string, each O(N), with constant-time set or array operations (since only 26 lowercase letters).
  • Time Complexity: O(N)
  • Space Complexity: O(N) for the right_unique array and O(1) for sets (since alphabet size is fixed).

Summary

The key to solving the "Number of Good Ways to Split a String" problem efficiently is to avoid redundant work by tracking unique character counts incrementally as we move through the string. By making two passes (one from right to left and one from left to right) and using simple data structures to record unique counts, we can solve the problem in linear time. This approach is both elegant and highly efficient, especially for large input sizes.

Code Implementation

class Solution:
    def numSplits(self, s: str) -> int:
        n = len(s)
        right_unique = [0] * n
        seen = set()
        for i in range(n-1, -1, -1):
            seen.add(s[i])
            right_unique[i] = len(seen)
        seen.clear()
        ans = 0
        left_unique = 0
        for i in range(n-1):
            seen.add(s[i])
            left_unique = len(seen)
            if left_unique == right_unique[i+1]:
                ans += 1
        return ans
      

class Solution {
public:
    int numSplits(string s) {
        int n = s.size();
        vector<int> right_unique(n, 0);
        unordered_set<char> seen;
        for (int i = n - 1; i >= 0; --i) {
            seen.insert(s[i]);
            right_unique[i] = seen.size();
        }
        seen.clear();
        int ans = 0;
        for (int i = 0; i < n - 1; ++i) {
            seen.insert(s[i]);
            int left_unique = seen.size();
            if (left_unique == right_unique[i + 1]) {
                ++ans;
            }
        }
        return ans;
    }
};
      

import java.util.*;
class Solution {
    public int numSplits(String s) {
        int n = s.length();
        int[] rightUnique = new int[n];
        Set<Character> seen = new HashSet<>();
        for (int i = n - 1; i >= 0; --i) {
            seen.add(s.charAt(i));
            rightUnique[i] = seen.size();
        }
        seen.clear();
        int ans = 0;
        for (int i = 0; i < n - 1; ++i) {
            seen.add(s.charAt(i));
            int leftUnique = seen.size();
            if (leftUnique == rightUnique[i + 1]) {
                ans++;
            }
        }
        return ans;
    }
}
      

var numSplits = function(s) {
    const n = s.length;
    const rightUnique = new Array(n).fill(0);
    const seen = new Set();
    for (let i = n - 1; i >= 0; --i) {
        seen.add(s[i]);
        rightUnique[i] = seen.size;
    }
    seen.clear();
    let ans = 0;
    for (let i = 0; i < n - 1; ++i) {
        seen.add(s[i]);
        let leftUnique = seen.size;
        if (leftUnique === rightUnique[i + 1]) {
            ans++;
        }
    }
    return ans;
};