Count beautiful splits in an array

Array Dynamic Programming

18.6% acceptance

Feb 24, 2026

105

You are given an array nums. A split of an array nums is beautiful if: The array nums is split into three subarrays: nums1, nums2, and nums3, such that nums can be formed by concatenating nums1, nums2, and nums3 in that order. The subarray nums1 is a prefix of nums2 OR nums2 is a prefix of nums3. Return the number of ways you can make this split.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn beautiful_splits(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    // Precompute LCP array: lcp[i][j] = length of longest common prefix of nums[i..] and nums[j..]
    // Use DP: lcp[i][j] = 0 if nums[i] != nums[j], else 1 + lcp[i+1][j+1]
    let mut lcp = vec![vec![0usize; n + 1]; n + 1];
    for i in (0..n).rev() {
      for j in (0..n).rev() {
        if nums[i] == nums[j] {
          lcp[i][j] = 1 + lcp[i+1][j+1];
        }
      }
    }
    
    // is_prefix(a, b, len_a): is nums[a..a+len_a] a prefix of nums[b..]?
    // i.e., lcp[a][b] >= len_a
    
    let mut ans = 0i32;
    // Split at i (nums1 = nums[0..i], len1 = i) and j (nums2 = nums[i..j], len2 = j-i)
    // nums3 = nums[j..], len3 = n-j
    // Conditions: i >= 1, j-i >= 1, n-j >= 1
    for i in 1..n {
      for j in (i+1)..n {
        let len1 = i;
        let len2 = j - i;
        // Check: nums1 is prefix of nums2 => len2 >= len1 AND lcp[0][i] >= len1
        let cond1 = len2 >= len1 && lcp[0][i] >= len1;
        // Check: nums2 is prefix of nums3 => len3 >= len2 AND lcp[i][j] >= len2
        let len3 = n - j;
        let cond2 = len3 >= len2 && lcp[i][j] >= len2;
        if cond1 || cond2 {
          ans += 1;
        }
      }
    }
    ans
  }
}