Scale Engineer

Number of Good Ways to Split a String

Med
#1406Time: O(N^2), where N is the length of the string. The outer loop runs N-1 times. Inside the loop, creating substrings and iterating over them to count distinct characters takes O(N) time. Thus, the total time complexity is (N-1) * O(N) = O(N^2).Space: O(N), where N is the length of the string. In each iteration, new substrings are created, which can take up to O(N) space. The HashSets take O(K) space where K is the alphabet size (a constant, 26), but the substring space dominates.
Patterns
Dynamic ProgrammingBit Manipulation
Data structures
Hash TableString

Prompt

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:

"aacaba"

Example 2:

Input: s = "abcd"
Output: 1
Explanation: Split the string as follows ("ab", "cd").

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. It iterates through every possible way to split the string into two non-empty parts. For each split, it calculates the number of unique characters in the left and right substrings independently and compares them. While straightforward, this method is inefficient because it repeatedly recalculates character counts for overlapping substrings.

Algorithm

  • Initialize a counter goodSplits to 0.
  • Iterate through all possible split points i from 1 to n-1, where n is the length of the string s.
  • For each i, create the left substring s_left = s.substring(0, i) and the right substring s_right = s.substring(i).
  • Use a HashSet to count the number of distinct characters in s_left.
  • Use another HashSet to count the number of distinct characters in s_right.
  • If the two counts are equal, increment goodSplits.
  • After the loop finishes, return goodSplits.

Walkthrough

The algorithm considers every possible split point. A string of length n can be split in n-1 ways. We can loop from i = 1 to n-1, where i is the index where the split occurs. The left part of the string will be s[0...i-1] and the right part will be s[i...n-1].

For each split, we perform the following steps:

  1. Extract the left substring, s_left.
  2. Extract the right substring, s_right.
  3. Create a HashSet for s_left. Iterate through its characters and add them to the set. The size of the set gives the number of distinct characters.
  4. Do the same for s_right with a new HashSet.
  5. If the sizes of the two sets are equal, we have found a 'good' split, so we increment a counter.

This process is repeated for all n-1 possible splits.

import java.util.HashSet;import java.util.Set; class Solution {    public int numSplits(String s) {        int n = s.length();        int goodSplits = 0;         // Iterate through all possible split points        for (int i = 1; i < n; i++) {            String s_left = s.substring(0, i);            String s_right = s.substring(i);             Set<Character> leftChars = new HashSet<>();            for (char c : s_left.toCharArray()) {                leftChars.add(c);            }             Set<Character> rightChars = new HashSet<>();            for (char c : s_right.toCharArray()) {                rightChars.add(c);            }             if (leftChars.size() == rightChars.size()) {                goodSplits++;            }        }        return goodSplits;    }}

Complexity

Time

O(N^2), where N is the length of the string. The outer loop runs N-1 times. Inside the loop, creating substrings and iterating over them to count distinct characters takes O(N) time. Thus, the total time complexity is (N-1) * O(N) = O(N^2).

Space

O(N), where N is the length of the string. In each iteration, new substrings are created, which can take up to O(N) space. The HashSets take O(K) space where K is the alphabet size (a constant, 26), but the substring space dominates.

Trade-offs

Pros

  • Very simple to understand and implement.

  • It is a direct and literal interpretation of the problem description.

Cons

  • Highly inefficient due to repeated work.

  • Creating substrings and populating hash sets in each iteration is computationally expensive.

  • This solution will likely result in a 'Time Limit Exceeded' error for inputs that are close to the constraints.

Solutions

class Solution { public int numSplits ( String s ) { Map < Character , Integer > cnt = new HashMap <>(); for ( char c : s . toCharArray ()) { cnt . merge ( c , 1 , Integer: : sum ); } Set < Character > vis = new HashSet <>(); int ans = 0 ; for ( char c : s . toCharArray ()) { vis . add ( c ); if ( cnt . merge ( c , - 1 , Integer: : sum ) == 0 ) { cnt . remove ( c ); } if ( vis . size () == cnt . size ()) { ++ ans ; } } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem