Ways to Split String

Given a string S, we can split S into 2 strings: S1 and S2. Return the number of ways S can be split such that the number of unique characters between S1 and S2 are the same.

Example 1:

Input: “aaaa” Output: 3 Explanation: we can get a - aaa, aa - aa, aaa- a Example 2:

Input: “bac” Output: 0 Example 3:

Input: “ababa” Output: 2 Explanation: ab - aba, aba - ba

Here is an approach to count the number of ways to split a string S into S1 and S2 such that S1 and S2 have the same number of unique characters:

  1. Create a set to store unique characters seen so far.

  2. Iterate through the string:

  • Add the current character to the set of seen characters.

  • If the number of unique characters equals half the current index, we have a valid split point. Increment the result counter.

  • Repeat for all indices, skipping the ones where number of unique chars does not equal half the index.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def countSplits(S):
  result = 0
  seen = set()

  for i in range(len(S)):
    seen.add(S[i])
    if len(seen) == i // 2:
      result += 1

  return result

The key steps are:

  • Track number of unique chars up to current index
  • Check if it equals half index as a potential split point
  • Increment result if split point found

We iterate through, finding all indices where the unique char criteria is met, to count all valid split ways.

The time complexity of this solution is O(N) where N is the length of the input string S.

The main operations are:

  • Iterating through the string once - O(N)
  • Adding each character to a hash set - O(1) per character, so O(N) total
  • Checking if unique char count equals half index - O(1)
  • Incrementing result - O(1)

So overall, this involves one pass through the string with constant time operations at each index.

The major steps are:

  1. Iteration - O(N)
  2. Adding to set - O(N)
  3. Checking count - O(1)
  4. Incrementing counter - O(N)

Since these are all done sequentially in one loop, the overall time complexity is O(N + N + N) = O(N).

We only loop through the string once and do not have any nested iterations. So the time complexity is linear in the input size N, making this an efficient linear time solution.