Problem

You are given an array nums.

A split of an array nums is beautiful if:

  1. 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.
  2. 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.

Examples

Example 1

1
2
3
4
5
6

Input: nums = [1,1,2,1]
Output: 2
Explanation:
The beautiful splits are:
1. A split with `nums1 = [1]`, `nums2 = [1,2]`, `nums3 = [1]`.
2. A split with `nums1 = [1]`, `nums2 = [1]`, `nums3 = [2,1]`.

Example 2

1
2
3
4

Input: nums = [1,2,3,4]
Output: 0
Explanation:
There are 0 beautiful splits.

Constraints

  • 1 <= nums.length <= 5000
  • 0 <= nums[i] <= 50

Solution

Method 1 – Prefix and Suffix Hashing 1

Intuition

To efficiently check if one subarray is a prefix of another, we can use rolling hash or tuple comparison. For each possible split, we check if nums1 is a prefix of nums2 or nums2 is a prefix of nums3. We iterate over all possible splits and count the valid ones.

Approach

  1. Iterate over all possible split points (i, j) such that 1 ≤ i < j < n.
  2. For each split:
    • nums1 = nums[0:i], nums2 = nums[i:j], nums3 = nums[j:n].
    • Check if nums1 is a prefix of nums2 (i ≤ j-i and nums1 == nums2[0:i]).
    • Check if nums2 is a prefix of nums3 (j-i ≤ n-j and nums2 == nums3[0:j-i]).
  3. Count the number of splits where either condition is true.
  4. Return the count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int countBeautifulSplits(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for (int i = 1; i < n-1; ++i) {
            for (int j = i+1; j < n; ++j) {
                int len1 = i, len2 = j-i, len3 = n-j;
                bool cond1 = len1 <= len2 && equal(nums.begin(), nums.begin()+len1, nums.begin()+i);
                bool cond2 = len2 <= len3 && equal(nums.begin()+i, nums.begin()+j, nums.begin()+j);
                if (cond1 || cond2) ans++;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func countBeautifulSplits(nums []int) int {
    n, ans := len(nums), 0
    for i := 1; i < n-1; i++ {
        for j := i+1; j < n; j++ {
            len1, len2, len3 := i, j-i, n-j
            cond1 := len1 <= len2 && slices.Equal(nums[:len1], nums[i:j][:len1])
            cond2 := len2 <= len3 && slices.Equal(nums[i:j], nums[j:][:len2])
            if cond1 || cond2 {
                ans++
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int countBeautifulSplits(int[] nums) {
        int n = nums.length, ans = 0;
        for (int i = 1; i < n-1; ++i) {
            for (int j = i+1; j < n; ++j) {
                int len1 = i, len2 = j-i, len3 = n-j;
                boolean cond1 = len1 <= len2 && Arrays.equals(Arrays.copyOfRange(nums, 0, len1), Arrays.copyOfRange(nums, i, i+len1));
                boolean cond2 = len2 <= len3 && Arrays.equals(Arrays.copyOfRange(nums, i, j), Arrays.copyOfRange(nums, j, j+len2));
                if (cond1 || cond2) ans++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun countBeautifulSplits(nums: IntArray): Int {
        val n = nums.size
        var ans = 0
        for (i in 1 until n-1) {
            for (j in i+1 until n) {
                val len1 = i
                val len2 = j-i
                val len3 = n-j
                val cond1 = len1 <= len2 && nums.slice(0 until len1) == nums.slice(i until i+len1)
                val cond2 = len2 <= len3 && nums.slice(i until j) == nums.slice(j until j+len2)
                if (cond1 || cond2) ans++
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def countBeautifulSplits(self, nums: list[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(1, n-1):
            for j in range(i+1, n):
                len1 = i
                len2 = j-i
                len3 = n-j
                cond1 = len1 <= len2 and nums[:len1] == nums[i:i+len1]
                cond2 = len2 <= len3 and nums[i:j] == nums[j:j+len2]
                if cond1 or cond2:
                    ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn count_beautiful_splits(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        for i in 1..n-1 {
            for j in i+1..n {
                let len1 = i;
                let len2 = j-i;
                let len3 = n-j;
                let cond1 = len1 <= len2 && nums[..len1] == nums[i..i+len1];
                let cond2 = len2 <= len3 && nums[i..j] == nums[j..j+len2];
                if cond1 || cond2 {
                    ans += 1;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    countBeautifulSplits(nums: number[]): number {
        const n = nums.length;
        let ans = 0;
        for (let i = 1; i < n-1; ++i) {
            for (let j = i+1; j < n; ++j) {
                const len1 = i, len2 = j-i, len3 = n-j;
                const cond1 = len1 <= len2 && nums.slice(0, len1).join(',') === nums.slice(i, i+len1).join(',');
                const cond2 = len2 <= len3 && nums.slice(i, j).join(',') === nums.slice(j, j+len2).join(',');
                if (cond1 || cond2) ans++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 * m), where n is the length of nums and m is the maximum subarray length compared.
  • 🧺 Space complexity: O(1), ignoring input and output storage.