How to Solve Number of Good Ways to Split a String

The solution tracks the distinct letter counts on both sides of each possible split. By using two hash maps to maintain left and right character frequencies dynamically, you can iterate through the string in one pass to check each split efficiently. This approach ensures O(n) time complexity with careful state transitions and avoids redundant recomputation of distinct counts.

Problem Statement

Given a string s, you can split it into two non-empty parts sleft and sright at any index. A split is considered good if the number of unique letters in sleft equals the number of unique letters in sright. Your task is to determine how many such good splits exist for the input string s.

For example, given s = "aacaba", there are multiple ways to split, but only the splits ("aac", "aba") and ("aaca", "ba") have equal distinct letters on both sides. Return the total count of these good splits. Constraints: 1 <= s.length <= 10^5 and s contains only lowercase English letters.

Examples

Example 1

Input: s = "aacaba"

Output: 2

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

Split the string as follows ("ab", "cd").

Constraints

• 1 <= s.length <= 105
• s consists of only lowercase English letters.

Solution Approach

Use Two Hash Maps to Track Counts

Initialize two hash maps: leftCount and rightCount. Populate rightCount with the frequency of all characters. Iterate through s, moving one character at a time from rightCount to leftCount, updating counts. If the number of keys in leftCount equals keys in rightCount, increment the result. This leverages the state transition dynamic programming pattern by maintaining valid character states efficiently.

Optimize with Single Pass

Instead of recomputing distinct counts at every split, update counts incrementally for each index. Removing characters from rightCount and adding to leftCount at each step ensures O(n) time. This prevents repeated scanning of substrings and avoids the main failure mode of naive solutions that try to count distinct letters from scratch for every possible split.

Consider Edge Cases

Handle minimal strings (length 1) where no split is possible. Ensure updates of counts remove entries when frequency reaches zero to keep key counts accurate. This avoids off-by-one errors in dynamic state tracking, which is the main pitfall in this problem's state transition approach.

Complexity Analysis

Time complexity is O(n) because each character is moved once between leftCount and rightCount. Space complexity is O(1) in practice, as there are at most 26 lowercase letters stored in the hash maps.

What Interviewers Usually Probe

• Checking if the candidate updates counts efficiently rather than recomputing distinct letters from scratch.
• Observing whether the candidate recognizes the problem as a state transition DP pattern with hash maps.
• Looking for handling of edge cases where strings are too short for any valid split.

Common Pitfalls or Variants

Common pitfalls

• Recomputing distinct characters for every split, causing O(n^2) time and timeout on large inputs.
• Forgetting to remove letters from rightCount when their count reaches zero, which inflates the distinct count incorrectly.
• Ignoring edge cases with minimal string length or repeated characters leading to wrong good split count.

Follow-up variants

• Count good splits when ignoring case sensitivity for letters.
• Return all the indices where good splits occur instead of just the count.
• Allow Unicode characters, requiring more generic hash maps for character tracking.

How GhostInterview Helps

• GhostInterview generates a step-by-step strategy to maintain left and right distinct counts with dynamic hash maps.
• It highlights the incremental state transitions that prevent naive O(n^2) computations and ensures correct good split counting.
• Provides automatic checks for edge cases and subtle off-by-one errors in split logic, improving solution robustness.

Topic Pages

• Hash Table
• String
• Dynamic Programming
• Bit Manipulation

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What defines a good split in this problem?

A split of s into sleft and sright is good if both sides contain the same number of distinct letters.

Can this be solved without hash maps?

Using arrays for fixed lowercase letters is possible, but hash maps generalize better for dynamic state transition tracking.

What is the key pattern used in this problem?

The problem uses a state transition dynamic programming pattern to maintain and compare distinct letter counts efficiently.

How to handle very long strings efficiently?

Incrementally update leftCount and rightCount while iterating to ensure O(n) time instead of recomputing distinct letters repeatedly.

What common mistakes should I avoid?

Avoid recomputing distinct counts at every split and remember to remove characters from the right hash map when their count reaches zero.