Problem

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 ofgood splits you can make in s.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3

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

Constraints

  • 1 <= s.length <= 10^5
  • s consists of only lowercase English letters.

Solution

Method 1 – Prefix and Suffix Distinct Count

Intuition

For each split, we need the number of distinct letters in the left and right substrings. We can precompute prefix and suffix distinct counts in O(n) time using two passes.

Approach

  1. Traverse s from left to right, for each position, store the number of distinct letters seen so far (prefix).
  2. Traverse s from right to left, for each position, store the number of distinct letters seen so far (suffix).
  3. For each split, compare prefix[i] and suffix[i+1]. If equal, increment answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
    int numSplits(string s) {
        int n = s.size();
        vector<int> left(n), right(n);
        unordered_set<char> seen;
        for (int i = 0; i < n; ++i) {
            seen.insert(s[i]);
            left[i] = seen.size();
        }
        seen.clear();
        for (int i = n-1; i >= 0; --i) {
            seen.insert(s[i]);
            right[i] = seen.size();
        }
        int ans = 0;
        for (int i = 0; i < n-1; ++i) {
            if (left[i] == right[i+1]) ++ans;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func numSplits(s string) int {
    n := len(s)
    left, right := make([]int, n), make([]int, n)
    seen := make(map[byte]bool)
    cnt := 0
    for i := 0; i < n; i++ {
        if !seen[s[i]] { cnt++; seen[s[i]] = true }
        left[i] = cnt
    }
    seen = make(map[byte]bool); cnt = 0
    for i := n-1; i >= 0; i-- {
        if !seen[s[i]] { cnt++; seen[s[i]] = true }
        right[i] = cnt
    }
    ans := 0
    for i := 0; i < n-1; i++ {
        if left[i] == right[i+1] { ans++ }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class Solution {
    public int numSplits(String s) {
        int n = s.length();
        int[] left = new int[n], right = new int[n];
        Set<Character> seen = new HashSet<>();
        for (int i = 0; i < n; ++i) {
            seen.add(s.charAt(i));
            left[i] = seen.size();
        }
        seen.clear();
        for (int i = n-1; i >= 0; --i) {
            seen.add(s.charAt(i));
            right[i] = seen.size();
        }
        int ans = 0;
        for (int i = 0; i < n-1; ++i) {
            if (left[i] == right[i+1]) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun numSplits(s: String): Int {
        val n = s.length
        val left = IntArray(n)
        val right = IntArray(n)
        val seen = mutableSetOf<Char>()
        for (i in 0 until n) {
            seen.add(s[i])
            left[i] = seen.size
        }
        seen.clear()
        for (i in n-1 downTo 0) {
            seen.add(s[i])
            right[i] = seen.size
        }
        var ans = 0
        for (i in 0 until n-1) {
            if (left[i] == right[i+1]) ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def numSplits(self, s: str) -> int:
        n = len(s)
        left, right = [0]*n, [0]*n
        seen = set()
        for i in range(n):
            seen.add(s[i])
            left[i] = len(seen)
        seen.clear()
        for i in range(n-1, -1, -1):
            seen.add(s[i])
            right[i] = len(seen)
        ans = 0
        for i in range(n-1):
            if left[i] == right[i+1]:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

use std::collections::HashSet;
impl Solution {
    pub fn num_splits(s: String) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut left = vec![0; n];
        let mut right = vec![0; n];
        let mut seen = HashSet::new();
        for i in 0..n {
            seen.insert(s[i]);
            left[i] = seen.len();
        }
        seen.clear();
        for i in (0..n).rev() {
            seen.insert(s[i]);
            right[i] = seen.len();
        }
        let mut ans = 0;
        for i in 0..n-1 {
            if left[i] == right[i+1] { ans += 1; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    numSplits(s: string): number {
        const n = s.length;
        const left = Array(n).fill(0), right = Array(n).fill(0);
        const seen = new Set<string>();
        for (let i = 0; i < n; ++i) {
            seen.add(s[i]);
            left[i] = seen.size;
        }
        seen.clear();
        for (let i = n-1; i >= 0; --i) {
            seen.add(s[i]);
            right[i] = seen.size;
        }
        let ans = 0;
        for (let i = 0; i < n-1; ++i) {
            if (left[i] === right[i+1]) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s.
  • 🧺 Space complexity: O(n).