Number of Good Ways to Split a String solution and explanation
Google
9 more videos on this problem
number of good ways to split a string leetcode | leetcode 1525Naresh Gupta · 9:09 · 6K views
LeetCode 1525. Number of Good Ways to Split a String - Interview Prep Ep 84Fisher Coder · 9:18 · 4K views
Number of Good Ways to Split a String || LeetcodePepcoding · 17:26 · 4K views
Google Coding Interview Question | Leetcode 1525 | Number of Good Ways to Split a StringWorkWithGoogler · 10:17 · 1K views
16. Number of Good Ways to Split a String | Dynamic Programming | LeetCode Medium 1525AceCoder Academy · 21:49 · 604 views
1525. Number of Good Ways to Split a StringChhavi Bansal · 15:19 · 584 views
1525. Number of Good Ways to Split a String (Leetcode Medium)Programming Live with Larry · 9:56 · 427 views
Number of Good Ways to Split a String (Leetcode 1525)Coding Interviews · 18:55 · 270 views
Number of Good Ways to Split a String | Leetcode 1525Competitive Coding · 9:54 · 235 views
1525.Number of Good ways to split string|leetcode dp series|leetcodeDp wale · 5:31 · 158 views
The problem
You are given a string s.
A split is called good if you can split s into two non-empty strings sleft and sright where their concatenation is equal to s (i.e., sleft + sright = s) and the number of distinct letters in sleft and sright is the same.
Return the number of good splits you can make in s.
Example 1:
Input: s = "aacaba"
Output: 2
Explanation: There are 5 ways to split "aacaba" and 2 of them are good.
("a", "acaba") Left string and right string contains 1 and 3 different letters respectively.
("aa", "caba") Left string and right string contains 1 and 3 different letters respectively.
("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.
Example 2:
Input: s = "abcd"
Output: 1
Explanation: Split the string as follows ("ab", "cd").
Constraints:
1 <= s.length <= 105sconsists of only lowercase English letters.
Approach overview
Problem Overview: You are given a string s. Split it into two non-empty parts and count how many split positions produce the same number of distinct characters on the left and right sides.
The challenge is computing distinct character counts efficiently for every split. A naive approach recomputes sets repeatedly, which becomes expensive. Efficient solutions track distinct counts incrementally using arrays or hash-based tracking.
Approach 1: Prefix and Suffix Distinct Count Arrays (O(n) time, O(n) space)
This approach precomputes the number of unique characters seen from both directions. First iterate left to right and store the distinct count at each index in a prefix array. Use a hash set or frequency array to track characters you've already encountered. Then iterate from right to left and build a suffix array that stores distinct counts for the substring starting at each index.
Once both arrays are built, check every split position i. If prefix[i] equals suffix[i+1], that split is valid. Increment the answer. Each character is processed a constant number of times, giving O(n) time. The tradeoff is the additional O(n) memory for the two arrays.
This technique appears frequently in string problems where information about prefixes and suffixes must be reused across many positions.
Approach 2: Two-Pass with Single Array (O(n) time, O(n) space)
You can reduce memory usage by storing only one side explicitly. First compute the suffix distinct counts and store them in an array. Then iterate from the left while maintaining a set (or frequency array) of characters already seen. Each step updates the left-side distinct count dynamically.
At index i, compare the current left distinct count with the precomputed suffix[i+1]. If they match, the split is good. This avoids building a separate prefix array and keeps the algorithm simple.
The logic relies on constant-time character tracking using either a frequency array of size 26 (for lowercase letters) or a hash table. Overall complexity remains O(n) time with O(n) space due to the suffix array.
This pattern resembles prefix-style preprocessing often seen in dynamic programming and counting problems where you reuse earlier results instead of recomputing them.
Recommended for interviews: Interviewers typically expect the prefix/suffix distinct counting idea. It demonstrates that you can transform repeated substring computations into a linear scan. Starting with the brute-force idea (rebuilding sets for every split) shows understanding of the problem, but the optimal O(n) solution shows algorithmic maturity and familiarity with prefix-based preprocessing.
Approach 1: Approach 1: Prefix and Suffix Distinct Count Arrays
In this approach, we utilize two arrays: left_distinct to count distinct characters from the start to each character, and right_distinct from each character to the end of the string. Using these arrays, we can easily compare the number of distinct characters on both sides of any potential split position.
First, we traverse the string from left to right to fill left_distinct, counting distinct characters as we go. Similarly, we populate right_distinct by traversing from right to left. Finally, we iterate through both arrays and compare values at each position to tally the number of good splits.
def num_good_splits(s: str) -> int:
n = len(s)
left_distinct = [0] * n
right_distinct = [0] * n
left_set, right_set = set(), set()
for i in range(n):
left_set.add(s[i])
left_distinct[i] = len(left_set)
for i in range(n - 1, -1, -1):
right_set.add(s[i])
right_distinct[i] = len(right_set)
return sum(left_distinct[i] == right_distinct[i + 1] for i in range(n - 1))
# Example usage
s = "aacaba"
print(num_good_splits(s))import java.util.HashSet;
public class GoodSplits {
public int numGoodSplits(String s) {
int n = s.length();
int[] leftDistinct = new int[n];
int[] rightDistinct = new int[n];
HashSet<Character> leftSet = new HashSet<>();
HashSet<Character> rightSet = new HashSet<>();
for (int i = 0; i < n; i++) {
leftSet.add(s.charAt(i));
leftDistinct[i] = leftSet.size();
}
for (int i = n - 1; i >= 0; i--) {
rightSet.add(s.charAt(i));
rightDistinct[i] = rightSet.size();
}
int goodSplits = 0;
for (int i = 0; i < n - 1; i++) {
if (leftDistinct[i] == rightDistinct[i + 1]) goodSplits++;
}
return goodSplits;
}
public static void main(String[] args) {
GoodSplits gs = new GoodSplits();
System.out.println(gs.numGoodSplits("aacaba"));
}
}#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
int numGoodSplits(string s) {
int n = s.size();
vector<int> left_distinct(n, 0), right_distinct(n, 0);
unordered_set<char> left_set, right_set;
for (int i = 0; i < n; ++i) {
left_set.insert(s[i]);
left_distinct[i] = left_set.size();
}
for (int i = n - 1; i >= 0; --i) {
right_set.insert(s[i]);
right_distinct[i] = right_set.size();
}
int good_splits = 0;
for (int i = 0; i < n - 1; ++i) {
if (left_distinct[i] == right_distinct[i + 1]) ++good_splits;
}
return good_splits;
}
int main() {
string s = "aacaba";
cout << numGoodSplits(s) << endl;
return 0;
}function numGoodSplits(s) {
const n = s.length;
const leftDistinct = Array(n).fill(0);
const rightDistinct = Array(n).fill(0);
const leftSet = new Set();
const rightSet = new Set();
for (let i = 0; i < n; i++) {
leftSet.add(s[i]);
leftDistinct[i] = leftSet.size;
}
for (let i = n - 1; i >= 0; i--) {
rightSet.add(s[i]);
rightDistinct[i] = rightSet.size;
}
let goodSplits = 0;
for (let i = 0; i < n - 1; i++) {
if (leftDistinct[i] === rightDistinct[i + 1]) goodSplits++;
}
return goodSplits;
}
// Example usage
const s = "aacaba";
console.log(numGoodSplits(s));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX_CHAR 26
int numGoodSplits(char* s) {
int n = strlen(s);
int left[MAX_CHAR] = {0}, right[MAX_CHAR] = {0};
int distinct_left = 0, distinct_right = 0;
int left_distinct[n], right_distinct[n];
for (int i = 0; i < n; i++) {
if (left[s[i] - 'a'] == 0) distinct_left++;
left[s[i] - 'a']++;
left_distinct[i] = distinct_left;
}
for (int i = n - 1; i >= 0; i--) {
if (right[s[i] - 'a'] == 0) distinct_right++;
right[s[i] - 'a']++;
right_distinct[i] = distinct_right;
}
int good_splits = 0;
for (int i = 0; i < n - 1; i++) {
if (left_distinct[i] == right_distinct[i+1]) good_splits++;
}
return good_splits;
}
int main() {
char s[] = "aacaba";
printf("%d\n", numGoodSplits(s));
return 0;
}using System;
using System.Collections.Generic;
class Program {
static int NumGoodSplits(string s) {
int n = s.Length;
int[] leftDistinct = new int[n];
int[] rightDistinct = new int[n];
HashSet<char> leftSet = new HashSet<char>();
HashSet<char> rightSet = new HashSet<char>();
for (int i = 0; i < n; i++) {
leftSet.Add(s[i]);
leftDistinct[i] = leftSet.Count;
}
for (int i = n - 1; i >= 0; i--) {
rightSet.Add(s[i]);
rightDistinct[i] = rightSet.Count;
}
int goodSplits = 0;
for (int i = 0; i < n - 1; i++) {
if (leftDistinct[i] == rightDistinct[i + 1]) goodSplits++;
}
return goodSplits;
}
static void Main() {
string s = "aacaba";
Console.WriteLine(NumGoodSplits(s));
}
}The Python function employs two lists to gauge distinct character counts from left and right. Sets assist in determining the diversity of characters in each portion of the string. The final loop checks for equaling counts at split points.
Time Complexity: O(n), as the string is read thoroughly twice.
Space Complexity: O(n), reflecting the use of two lists for distinct character storage.
Approach 2: Approach 2: Two-Pass with Single Array
This method reduces space consumption by employing a single array and two counters: one for distinct prefixes and another for suffixes. During the first pass, distinct prefix counts are recorded. The second backward pass updates this single array with suffix counts; simultaneously, good splits are counted when prefix and suffix counts align.
def num_good_splits(s: str) -> int:
n = len(s)
left_distinct = [0] * n
distinct_tracker = {}
distinct_count = 0
for i in range(n):
if s[i] not in distinct_tracker:
distinct_count += 1
distinct_tracker[s[i]] = distinct_tracker.get(s[i], 0) + 1
left_distinct[i] = distinct_count
distinct_tracker.clear()
distinct_count = 0
good_splits = 0
for i in range(n - 1, 0, -1):
if s[i] not in distinct_tracker:
distinct_count += 1
distinct_tracker[s[i]] = distinct_tracker.get(s[i], 0) + 1
if left_distinct[i - 1] == distinct_count:
good_splits += 1
return good_splits
# Example usage
s = "aacaba"
print(num_good_splits(s))import java.util.HashMap;
public class GoodSplits {
public int numGoodSplits(String s) {
int n = s.length();
int[] leftDistinct = new int[n];
HashMap<Character, Integer> map = new HashMap<>();
int distinctCount = 0;
for (int i = 0; i < n; i++) {
map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
if (map.get(s.charAt(i)) == 1) distinctCount++;
leftDistinct[i] = distinctCount;
}
map.clear();
distinctCount = 0;
int goodSplits = 0;
for (int i = n - 1; i > 0; i--) {
map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
if (map.get(s.charAt(i)) == 1) distinctCount++;
if (leftDistinct[i - 1] == distinctCount) goodSplits++;
}
return goodSplits;
}
public static void main(String[] args) {
GoodSplits gs = new GoodSplits();
System.out.println(gs.numGoodSplits("aacaba"));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int numGoodSplits(string s) {
int n = s.size();
unordered_map<char, int> distinct_tracker;
vector<int> left_distinct(n);
int distinct_count = 0;
for (int i = 0; i < n; ++i) {
if (distinct_tracker[s[i]]++ == 0) ++distinct_count;
left_distinct[i] = distinct_count;
}
distinct_tracker.clear();
distinct_count = 0;
int good_splits = 0;
for (int i = n - 1; i > 0; --i) {
if (distinct_tracker[s[i]]++ == 0) ++distinct_count;
if (left_distinct[i - 1] == distinct_count) ++good_splits;
}
return good_splits;
}
int main() {
string s = "aacaba";
cout << numGoodSplits(s) << endl;
return 0;
}function numGoodSplits(s) {
const n = s.length;
const leftDistinct = Array(n).fill(0);
const distinctTracker = {};
let distinctCount = 0;
for (let i = 0; i < n; i++) {
if (!distinctTracker[s[i]]) {
distinctCount++;
distinctTracker[s[i]] = 0;
}
distinctTracker[s[i]] += 1;
leftDistinct[i] = distinctCount;
}
Object.keys(distinctTracker).forEach(key => distinctTracker[key] = 0);
distinctCount = 0;
let goodSplits = 0;
for (let i = n - 1; i > 0; i--) {
if (!distinctTracker[s[i]]) {
distinctCount++;
distinctTracker[s[i]] = 0;
}
distinctTracker[s[i]] += 1;
if (leftDistinct[i - 1] === distinctCount) goodSplits++;
}
return goodSplits;
}
// Example usage
const s = "aacaba";
console.log(numGoodSplits(s));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX_CHAR 26
int numGoodSplits(char* s) {
int n = strlen(s);
int distinct_tracker[MAX_CHAR] = {0};
int left_distinct = 0;
int split_counts[n];
for (int i = 0; i < n; i++) {
if (distinct_tracker[s[i] - 'a']++ == 0) left_distinct++;
split_counts[i] = left_distinct;
}
memset(distinct_tracker, 0, sizeof(distinct_tracker));
int right_distinct = 0, good_splits = 0;
for (int i = n - 1; i > 0; i--) {
if (distinct_tracker[s[i] - 'a']++ == 0) right_distinct++;
if (split_counts[i - 1] == right_distinct) good_splits++;
}
return good_splits;
}
int main() {
char s[] = "aacaba";
printf("%d\n", numGoodSplits(s));
return 0;
}using System;
using System.Collections.Generic;
class Program {
static int NumGoodSplits(string s) {
int n = s.Length;
int[] leftDistinct = new int[n];
Dictionary<char, int> map = new Dictionary<char, int>();
int distinctCount = 0;
for (int i = 0; i < n; i++) {
if (!map.ContainsKey(s[i])) {
distinctCount++;
map[s[i]] = 0;
}
map[s[i]] += 1;
leftDistinct[i] = distinctCount;
}
map.Clear();
distinctCount = 0;
int goodSplits = 0;
for (int i = n - 1; i > 0; i--) {
if (!map.ContainsKey(s[i])) {
distinctCount++;
map[s[i]] = 0;
}
map[s[i]] += 1;
if (leftDistinct[i - 1] == distinctCount) goodSplits++;
}
return goodSplits;
}
static void Main() {
string s = "aacaba";
Console.WriteLine(NumGoodSplits(s));
}
}Python's implementation mirrors the single-array approach with a dictionary, preserving dynamic adjustments to track suffrage totals for interpreting good splits across the string.
Time Complexity: O(n), typical of multiple traversals.
Space Complexity: O(1), effectively constant given bounded character set
Approach 3: Default Approach
func numSplits(s string) (ans int) {
cnt := map[rune]int{}
for _, c := range s {
cnt[c]++
}
vis := map[rune]bool{}
for _, c := range s {
vis[c] = true
cnt[c]--
if cnt[c] == 0 {
delete(cnt, c)
}
if len(vis) == len(cnt) {
ans++
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Prefix and Suffix Distinct Count Arrays | Time Complexity: O(n), as the string is read thoroughly twice. |
| Approach 2: Two-Pass with Single Array | Time Complexity: O(n), typical of multiple traversals. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix and Suffix Distinct Count Arrays | O(n) | O(n) | Best general solution. Easy to reason about and commonly used in interviews. |
| Two-Pass with Single Array | O(n) | O(n) | When you want slightly cleaner logic by computing suffix counts first and updating prefix counts on the fly. |
Frequently asked questions
Is Number of Good Ways to Split a String easy or hard?
The problem is rated Medium on LeetCode. The logic is straightforward once you recognize the need for prefix and suffix distinct counts, but many candidates initially attempt slower approaches that recompute distinct characters for each split.
Number of Good Ways to Split a String Python/Java solution
In Python or Java, maintain a set or frequency array to track distinct characters while scanning the string. Build suffix distinct counts in one pass, then update prefix counts in another pass. This produces an O(n) solution that works efficiently for strings up to typical LeetCode limits.
How to solve Number of Good Ways to Split a String in O(n)?
First compute distinct character counts for all suffixes using a right-to-left pass. Then scan from left to right while maintaining a set or frequency array of seen characters. Compare the left distinct count with the stored suffix value at every split. Matching counts indicate a valid split.
What is the best approach for Number of Good Ways to Split a String?
The best approach uses prefix and suffix distinct character counts. Precompute the number of unique characters from the left and from the right, then compare them at every split position. This reduces the problem to a single linear scan with O(n) time and O(n) space.
Is Number of Good Ways to Split a String asked at Google/Amazon/Meta?
Problems involving prefix counts, distinct characters, and string partitioning frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this problem test your ability to preprocess strings efficiently and avoid repeated substring computations.
What data structure is used in Number of Good Ways to Split a String?
The solution typically uses a hash set, hash map, or a fixed-size frequency array to track distinct characters. Arrays are also used to store prefix or suffix distinct counts so they can be compared quickly for every split.
What is the time complexity of Number of Good Ways to Split a String?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed a constant number of times while building prefix or suffix distinct counts. Space complexity is O(n) for the auxiliary arrays used to store distinct counts.