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.

Description Hints 1 Solution Video 9:09

1525. Number of Good Ways to Split a String

Medium68.2% acceptance2 companies

You are given a string s.

A split is called good if you can split s into two non-empty strings s_left and s_right where their concatenation is equal to s (i.e., s_left + s_right = s) and the number of distinct letters in s_left and s_right 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 <= 10⁵
s consists of only lowercase English letters.

Asked at 2 companies

Google Amazon

Topics

Hints open one at a time

Hint 1

Use two HashMap to store the counts of distinct letters in the left and right substring divided by the current index.

9:09

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def numSplits(self, s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"aacaba"

Input

"abcd"

Your code is saved on this device.Solution