Number of Good Ways to Split a String

medium hash map string bit manipulation prefix sum counting

Problem

A split of a string s is good if s = p + q (both non-empty) and p and q have the same number of distinct letters. Count the number of good splits.

Inputs = "aacaba"

Output2

Splits "aac"|"aba" and "aaca"|"ba" both produce 2 distinct letters on each side.

from collections import Counter

def num_splits(s):
    right = Counter(s)
    left = {}
    ans = 0
    for ch in s[:-1]:
        left[ch] = left.get(ch, 0) + 1
        right[ch] -= 1
        if right[ch] == 0: del right[ch]
        if len(left) == len(right):
            ans += 1
    return ans

function numSplits(s) {
  const right = new Map();
  for (const c of s) right.set(c, (right.get(c) || 0) + 1);
  const left = new Map();
  let ans = 0;
  for (let i = 0; i < s.length - 1; i++) {
    const c = s[i];
    left.set(c, (left.get(c) || 0) + 1);
    right.set(c, right.get(c) - 1);
    if (right.get(c) === 0) right.delete(c);
    if (left.size === right.size) ans++;
  }
  return ans;
}

class Solution {
    public int numSplits(String s) {
        Map<Character, Integer> right = new HashMap<>();
        for (char c : s.toCharArray()) right.merge(c, 1, Integer::sum);
        Map<Character, Integer> left = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            char c = s.charAt(i);
            left.merge(c, 1, Integer::sum);
            right.merge(c, -1, Integer::sum);
            if (right.get(c) == 0) right.remove(c);
            if (left.size() == right.size()) ans++;
        }
        return ans;
    }
}

int numSplits(string s) {
    unordered_map<char, int> right, left;
    for (char c : s) right[c]++;
    int ans = 0;
    for (int i = 0; i < (int)s.size() - 1; i++) {
        char c = s[i];
        left[c]++;
        if (--right[c] == 0) right.erase(c);
        if (left.size() == right.size()) ans++;
    }
    return ans;
}

Explanation

A split is "good" when the left piece and right piece have the same number of distinct letters. Checking every split from scratch would be slow, so instead we maintain two running letter-count maps and slide the dividing line one step at a time.

We start with right holding the counts of all letters and left empty. Then for each position we move one character from the right side to the left: increment its count in left, decrement in right, and when a count in right hits 0 we delete that key so it no longer counts as distinct.

After each move, the number of distinct letters on each side is just the size of each map. If left.size == right.size, this split is good and we add one to the answer.

Example: s = "aacaba". Sliding the divider, the splits "aac"|"aba" and "aaca"|"ba" each leave 2 distinct letters on both sides, so the count of good splits is 2.

Time: O(n) Space: O(26)