Number of Good Ways to Split a String
Problem
s into two non-empty pieces: a left part
p and a right part q (so p + q == s). The cut is
good when p and q contain the same number of
distinct letters. Return how many of the n−1 possible cuts are good.s = "aacaba"Output2 ("aac|aba" and "aaca|ba")s = "abcd"Output1 ("ab|cd")s = "aaaaa"Output41 ≤ s.length ≤ 105 · s consists of lowercase English letters
Try it yourself
class Solution {
public int numSplits(String s) {
}
}
Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].
Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.
Open the Hashing & Counting guide →Approaches
Brute ForceRecount Both Sides per Cut
O(n2)Space O(1)For each of the n−1 cut positions, scan the left piece and the
right piece with a 26-slot boolean table and compare their distinct counts.
Each cut costs O(n), so the total is quadratic.
public int numSplits(String s) { int n = s.length(), good = 0; for (int cut = 1; cut < n; cut++) { if (distinct(s, 0, cut) == distinct(s, cut, n)) good++; } return good; } private int distinct(String s, int from, int to) { boolean[] seen = new boolean[26]; int count = 0; for (int i = from; i < to; i++) { int c = s.charAt(i) - 'a'; if (!seen[c]) { seen[c] = true; count++; } } return count; }
Direct translation of the definition; too slow for n = 105.
BetterPrefix & Suffix Distinct Arrays
O(n)Space O(n)Precompute pre[i] = distinct letters in s[0..i] with a
left-to-right sweep, and suf[i] = distinct letters in s[i..n-1]
with a right-to-left sweep. The cut after index i is good when
pre[i] == suf[i+1].
public int numSplits(String s) { int n = s.length(); int[] pre = new int[n], suf = new int[n]; boolean[] seen = new boolean[26]; int count = 0; for (int i = 0; i < n; i++) { int c = s.charAt(i) - 'a'; if (!seen[c]) { seen[c] = true; count++; } pre[i] = count; } seen = new boolean[26]; count = 0; for (int i = n - 1; i >= 0; i--) { int c = s.charAt(i) - 'a'; if (!seen[c]) { seen[c] = true; count++; } suf[i] = count; } int good = 0; for (int i = 0; i + 1 < n; i++) { if (pre[i] == suf[i + 1]) good++; } return good; }
Linear time, but stores two extra arrays of length n.
OptimalOne Sweep with Two Frequency Tables
O(n)Space O(1)Start with every letter on the right (count them, note how many are distinct). Move
characters one by one to the left: a letter adds to leftDistinct on its
first arrival, and removes from rightDistinct when its right count drops to
0. Compare after each move.
public int numSplits(String s) { int[] right = new int[26]; int rightDistinct = 0; for (int i = 0; i < s.length(); i++) { if (right[s.charAt(i) - 'a']++ == 0) rightDistinct++; } boolean[] inLeft = new boolean[26]; int leftDistinct = 0, good = 0; for (int i = 0; i + 1 < s.length(); i++) { // the right side must stay non-empty int c = s.charAt(i) - 'a'; if (!inLeft[c]) { inLeft[c] = true; leftDistinct++; } if (--right[c] == 0) rightDistinct--; if (leftDistinct == rightDistinct) good++; } return good; }
Dry runs = "aacaba"
- i=0aiacabaL=1 R=3
- i=1aaicabaL=1 R=3
- i=2aaciabaL=2 R=2 good=1
- i=3aacaibaL=2 R=2 good=2
- i=4aacabiaL=3 R=1 → 2 ✔
Single pass after counting, only two 26-slot tables — best possible.
n−2: moving the last character left would leave an
empty right part, which is not a legal split.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Recount Both Sides per Cut | O(n2) | O(1) |
| Better | Prefix & Suffix Distinct Arrays | O(n) | O(n) |
| Optimal | One Sweep with Two Frequency Tables | O(n) | O(1) |
- Allowing an empty left or right part — only cuts 1..n−1 count.
- Comparing total lengths or letter counts instead of distinct letters.
- Off-by-one between
pre[i]andsuf[i+1]in the array version.
- Point out monotonicity: left distinct never decreases, right distinct never increases.
- Mention you could binary-search the range of good cuts, but a sweep is simpler.
- Highlight that the alphabet is fixed (26), so the tables are O(1) space.