Skip to main content
Back to problems
#1525
Medium Algorithms

Number of good ways to split a string

Hash Table String Dynamic Programming Bit Manipulation
68.4% acceptance
Feb 25, 2026
2118
54
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.

Solution

Rust
Time O(n)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn num_splits(s: String) -> i32 {
    let bytes = s.as_bytes();
    let n = bytes.len();
    let mut left_distinct = vec![0i32; n];
    let mut right_distinct = vec![0i32; n];
    let mut seen = [0u32; 26];
    let mut cnt = 0i32;
    for i in 0..n {
      let c = (bytes[i] - b'a') as usize;
      seen[c] += 1;
      if seen[c] == 1 { cnt += 1; }
      left_distinct[i] = cnt;
    }
    seen = [0u32; 26];
    cnt = 0;
    for i in (0..n).rev() {
      let c = (bytes[i] - b'a') as usize;
      seen[c] += 1;
      if seen[c] == 1 { cnt += 1; }
      right_distinct[i] = cnt;
    }
    (0..n-1).filter(|&i| left_distinct[i] == right_distinct[i+1]).count() as i32
  }
}