# Count Beautiful Splits in an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-beautiful-splits-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/count-beautiful-splits-in-an-array
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## 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.

**Example 1:**

**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:**

**Input:** nums = \[1,2,3,4\]

**Output:** 0

**Explanation:**

There are 0 beautiful splits.

**Constraints:**

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

# Approaches
## Brute Force Iteration
The most straightforward method is to check every possible way to split the array into three non-empty subarrays. A split is defined by two indices, `i` and `j`, which mark the start of the second and third subarrays, respectively. We can iterate through all valid pairs of `(i, j)` and, for each pair, explicitly check if the split is beautiful by comparing the elements of the subarrays.
**Time:** O(N^3) - The two nested loops for `i` and `j` run in `O(N^2)`. Inside these loops, the prefix checks involve another loop that can run up to `O(N)` times in the worst case. · **Space:** O(1) - We only use a few variables to keep track of indices and the count, requiring constant extra space.
**Pros:** Simple to understand and implement.; Requires no complex data structures or algorithms.
**Cons:** Highly inefficient due to the nested loops and repeated linear scans for prefix checking.; Will likely result in a 'Time Limit Exceeded' error on platforms with strict time limits for the given constraints.
### Explanation
We use two nested loops to generate all possible split points. The outer loop for `i` runs from `1` to `n-2`, and the inner loop for `j` runs from `i+1` to `n-1`. For each pair `(i, j)`, we get three subarrays: `nums1 = nums[0...i-1]`, `nums2 = nums[i...j-1]`, and `nums3 = nums[j...n-1]`. We then check the two conditions for a beautiful split. Condition 1: `nums1` is a prefix of `nums2`. We compare `nums[k]` with `nums[i+k]` for `k` from `0` to `i-1`. This check is only possible if `length(nums1) <= length(nums2)`. Condition 2: `nums2` is a prefix of `nums3`. We compare `nums[i+k]` with `nums[j+k]` for `k` from `0` to `j-i-1`. This check is only possible if `length(nums2) <= length(nums3)`. If either of these conditions holds, we increment a counter. The final value of the counter is the answer.

```java
class Solution {
    public int countBeautifulSplits(int[] nums) {
        int n = nums.length;
        int count = 0;
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // nums1: [0, i-1], nums2: [i, j-1], nums3: [j, n-1]
                int len1 = i;
                int len2 = j - i;
                int len3 = n - j;

                boolean cond1 = false;
                if (len1 <= len2) {
                    boolean isPrefix = true;
                    for (int k = 0; k < len1; k++) {
                        if (nums[k] != nums[i + k]) {
                            isPrefix = false;
                            break;
                        }
                    }
                    if (isPrefix) {
                        cond1 = true;
                    }
                }

                boolean cond2 = false;
                if (len2 <= len3) {
                    boolean isPrefix = true;
                    for (int k = 0; k < len2; k++) {
                        if (nums[i + k] != nums[j + k]) {
                            isPrefix = false;
                            break;
                        }
                    }
                    if (isPrefix) {
                        cond2 = true;
                    }
                }

                if (cond1 || cond2) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a counter `count` to 0.
*   Iterate through all possible first split points `i` from `1` to `n-2` (where `n` is the length of the array).
*   Inside this loop, iterate through all possible second split points `j` from `i+1` to `n-1`.
*   These loops define three subarrays: `nums1 = nums[0...i-1]`, `nums2 = nums[i...j-1]`, and `nums3 = nums[j...n-1]`.
*   For each `(i, j)` pair, check the two conditions for a beautiful split:
    1.  **`nums1` is a prefix of `nums2`**: This is possible only if `length(nums1) <= length(nums2)`. If so, perform a linear scan to compare `nums[k]` with `nums[i+k]` for `k` from `0` to `i-1`.
    2.  **`nums2` is a prefix of `nums3`**: This is possible only if `length(nums2) <= length(nums3)`. If so, perform another linear scan to compare `nums[i+k]` with `nums[j+k]` for `k` from `0` to `j-i-1`.
*   If either of the two conditions is met, increment the `count`.
*   After all loops complete, return `count`.

## Dynamic Programming with LCP Table
The brute-force approach is slow due to the repeated work of comparing subarrays for prefix relationships. We can optimize this by pre-computing the lengths of the longest common prefixes (LCP) for all pairs of suffixes in the array. This allows us to check the prefix conditions in constant time.
**Time:** O(N^2) - The algorithm is dominated by two phases, both taking `O(N^2)`: building the LCP table and iterating through all possible splits. · **Space:** O(N^2) - The LCP table requires quadratic space.
**Pros:** Significantly faster than the brute-force approach.; Passes within time limits for the given constraints.
**Cons:** The `O(N^2)` space complexity can be problematic for large `N`, potentially exceeding memory limits.
### Explanation
We define `lcp[i][j]` as the length of the longest common prefix between the suffix starting at index `i` (`nums[i...]`) and the suffix starting at index `j` (`nums[j...]`). This `lcp` table can be filled using dynamic programming. The recurrence relation is: `lcp[i][j] = 1 + lcp[i+1][j+1]` if `nums[i] == nums[j]`, and `0` otherwise. We fill the table by iterating `i` and `j` from `n-1` down to `0`. After this `O(N^2)` pre-computation, we can answer any LCP query in `O(1)`. We then iterate through all split points `(i, j)` as in the brute-force approach. For each split, the conditions can be checked in `O(1)`: `nums1` is a prefix of `nums2` if `lcp[0][i] >= length(nums1)`, and `nums2` is a prefix of `nums3` if `lcp[i][j] >= length(nums2)`. This reduces the total time complexity to `O(N^2)`.

```java
class Solution {
    public int countBeautifulSplits(int[] nums) {
        int n = nums.length;
        int[][] lcp = new int[n + 1][n + 1];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (nums[i] == nums[j]) {
                    lcp[i][j] = 1 + lcp[i + 1][j + 1];
                }
            }
        }

        int count = 0;
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int len1 = i;
                int len2 = j - i;
                int len3 = n - j;

                boolean cond1 = false;
                if (len1 <= len2 && lcp[0][i] >= len1) {
                    cond1 = true;
                }

                boolean cond2 = false;
                if (len2 <= len3 && lcp[i][j] >= len2) {
                    cond2 = true;
                }

                if (cond1 || cond2) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Define a 2D array `lcp` of size `(n+1) x (n+1)`, where `lcp[i][j]` will store the length of the longest common prefix of suffixes `nums[i...]` and `nums[j...]`.
*   Populate the `lcp` table using dynamic programming. Iterate `i` and `j` from `n-1` down to `0`.
*   The recurrence relation is: `if (nums[i] == nums[j]) lcp[i][j] = 1 + lcp[i+1][j+1];` otherwise `lcp[i][j] = 0`.
*   After `lcp` is computed, initialize `count = 0`.
*   Iterate through all split points `(i, j)` with `i` from `1` to `n-2` and `j` from `i+1` to `n-1`.
*   For each split, check the conditions in `O(1)` time:
    1.  `nums1` is a prefix of `nums2`: `len1 <= len2 && lcp[0][i] >= len1`.
    2.  `nums2` is a prefix of `nums3`: `len2 <= len3 && lcp[i][j] >= len2`.
*   If either condition is true, increment `count`.
*   Return `count`.

## Optimized O(N^2) with Rolling Hash
We can achieve the same `O(N^2)` time complexity as the DP approach but with a much better `O(N)` space complexity by using polynomial rolling hash. Hashing allows us to compare any two subarrays for equality in `O(1)` time on average after an initial `O(N)` pre-computation.
**Time:** O(N^2) - `O(N)` for pre-computation of hashes and powers, followed by `O(N^2)` for iterating through all splits, with each check taking `O(1)` time. · **Space:** O(N) - We need two arrays of size `N` to store the prefix hashes and the powers of the base.
**Pros:** Optimal space complexity among `O(N^2)` time solutions.; Efficient in both time and space, making it a robust solution for the given constraints.; Conceptually simpler to implement than other advanced string algorithms like Z-algorithm or Suffix Trees.
**Cons:** Relies on hashing, which carries a small theoretical probability of collision (two different subarrays having the same hash). This risk can be minimized by using two different hash functions (double hashing).
### Explanation
First, we pre-compute the hash values for all prefixes of the `nums` array. We also pre-compute the powers of a chosen base `p`. This allows us to calculate the hash of any subarray `nums[i...j]` in `O(1)`. To increase reliability and avoid collisions, it's a good practice to use two different prime moduli and bases (double hashing), though a single hash is often sufficient for competitive programming problems. With the hashing utility ready, we iterate through all possible split points `(i, j)`. For each split, we check the two conditions by comparing the hashes of the relevant subarrays. Each check is `O(1)`, so the total time complexity remains `O(N^2)`. The space is dominated by the pre-computed hash and power arrays, which is `O(N)`.

```java
class Solution {
    public int countBeautifulSplits(int[] nums) {
        int n = nums.length;
        HashUtil hashUtil = new HashUtil(nums);
        
        int count = 0;
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int len1 = i;
                int len2 = j - i;
                int len3 = n - j;

                boolean cond1 = false;
                if (len1 <= len2) {
                    if (hashUtil.getHash(0, len1 - 1) == hashUtil.getHash(i, i + len1 - 1)) {
                        cond1 = true;
                    }
                }

                boolean cond2 = false;
                if (len2 <= len3) {
                    if (hashUtil.getHash(i, j - 1) == hashUtil.getHash(j, j + len2 - 1)) {
                        cond2 = true;
                    }
                }

                if (cond1 || cond2) {
                    count++;
                }
            }
        }
        return count;
    }
}

class HashUtil {
    private long[] prefixHash;
    private long[] powers;
    private long M = 1_000_000_007;
    private int P = 53; // nums[i] <= 50, so a prime > 51 is good.

    public HashUtil(int[] arr) {
        int n = arr.length;
        prefixHash = new long[n + 1];
        powers = new long[n + 1];
        powers[0] = 1;
        for (int i = 0; i < n; i++) {
            powers[i + 1] = (powers[i] * P) % M;
            // Add 1 to nums[i] to avoid hash of [0] being 0.
            prefixHash[i + 1] = (prefixHash[i] * P + (arr[i] + 1)) % M;
        }
    }

    public long getHash(int start, int end) {
        long len = end - start + 1;
        long hash = (prefixHash[end + 1] - (prefixHash[start] * powers[(int)len]) % M + M) % M;
        return hash;
    }
}
```
### Algorithm
*   Implement a helper class or structure for rolling hash calculations. This involves choosing a base `P` and a modulus `M`.
*   Pre-compute two arrays in `O(N)`: one for the powers of the base `P` (`powers[k] = P^k % M`) and another for the prefix hashes of the input array (`prefixHash[k]` = hash of `nums[0...k-1]`).
*   Create a function `getHash(start, end)` that uses the pre-computed arrays to return the hash of any subarray `nums[start...end]` in `O(1)` time.
*   Initialize `count = 0`.
*   Iterate through all split points `(i, j)` with `i` from `1` to `n-2` and `j` from `i+1` to `n-1`.
*   For each split, check the conditions by comparing hashes:
    1.  `nums1` is a prefix of `nums2`: `len1 <= len2 && getHash(0, len1-1) == getHash(i, i+len1-1)`.
    2.  `nums2` is a prefix of `nums3`: `len2 <= len3 && getHash(i, j-1) == getHash(j, j+len2-1)`.
*   If either condition is true, increment `count`.
*   Return `count`.

# Solutions
### Java

```java
class Solution {
public
  int beautifulSplits(int[] nums) {
    int n = nums.length;
    int[][] lcp = new int[n + 1][n + 1];
    for (int i = n - 1; i >= 0; i--) {
      for (int j = n - 1; j > i; j--) {
        if (nums[i] == nums[j]) {
          lcp[i][j] = lcp[i + 1][j + 1] + 1;
        }
      }
    }
    int ans = 0;
    for (int i = 1; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
        boolean a = (i <= j - i) && (lcp[0][i] >= i);
        boolean b = (j - i <= n - j) && (lcp[i][j] >= j - i);
        if (a || b) {
          ans++;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int beautifulSplits(vector<int> &nums) {
    int n = nums.size();
    vector<vector<int>> lcp(n + 1, vector<int>(n + 1, 0));
    for (int i = n - 1; i >= 0; i--) {
      for (int j = n - 1; j > i; j--) {
        if (nums[i] == nums[j]) {
          lcp[i][j] = lcp[i + 1][j + 1] + 1;
        }
      }
    }
    int ans = 0;
    for (int i = 1; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
        bool a = (i <= j - i) && (lcp[0][i] >= i);
        bool b = (j - i <= n - j) && (lcp[i][j] >= j - i);
        if (a || b) {
          ans++;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def beautifulSplits(self, nums: List[int]) -> int: n = len(nums) lcp = [[0] * (n + 1) for _ in range(n + 1)] for i in range(n - 1, - 1, - 1): for j in range(n - 1, i - 1, - 1): if nums[i] == nums[j]: lcp[i][j] = lcp[i + 1][j + 1] + 1 ans = 0 for i in range(1, n - 1): for j in range(i + 1, n): a = i <= j - i and lcp[0][i] >= i b = j - i <= n - j and lcp[i][j] >= j - i ans += int(a or b) return ans

```