Problem Description

You are given an array nums.

A split of an array nums is beautiful if:

1. The array nums is split into three non-empty 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.

Intuition

To solve the problem, we use the concept of Longest Common Prefix (LCP) between suffixes of the array. The LCP[i][j] table is built to store the length of the longest common prefix between the subarrays starting at indices i and j.

The problem requires us to check if either:

• nums1 is a prefix of nums2, which means LCP[0][i] must be at least i,
• or nums2 is a prefix of nums3, which is satisfied if LCP[i][j] is at least j - i.

To avoid redundant calculations, we preprocess the LCP table using a nested loop. Starting from the end of the array, if nums[i] == nums[j], we compute LCP[i][j] = LCP[i + 1][j + 1] + 1. This allows quick access to LCP information when evaluating each potential split of the array.

We then iterate over all possible indices to split the array into nums1, nums2, and nums3 and evaluate the above conditions. For each successful check, we increment the count of beautiful splits.

The solution is efficient for the problem constraints and captures all potential ways to form beautiful splits.

Learn more about Dynamic Programming patterns.

Solution Approach

To solve the problem of finding the number of beautiful splits in the array, we use a dynamic programming approach with the Longest Common Prefix (LCP) table. Here's a step-by-step breakdown of the solution:

1. Initialize LCP Table: We first initialize a 2D list lcp where lcp[i][j] will store the length of the longest common prefix of subarrays nums[i:] and nums[j:]. The table size is (n+1) x (n+1) to accommodate the indices properly, initialized with zeros.

2. Build LCP Table: We fill in the lcp table starting from the end of the array. For each pair of indices (i, j):

   • If nums[i] == nums[j], then lcp[i][j] = lcp[i + 1][j + 1] + 1. This means if the current elements are the same, the common prefix length is extended by one, based on the previously calculated LCP.

3. Enumerate Possible Splits: We then iterate over possible indices i and j, where:

   • i is the end index for the first subarray nums1.
   • j is the end index for the second subarray nums2.

4. Check Beautiful Split Condition: For each possible pair (i, j):

   • Check if nums1 is a prefix of nums2. This is true if i <= j - i and lcp[0][i] >= i.
   • Alternatively, check if nums2 is a prefix of nums3. This is true if j - i <= n - j and lcp[i][j] >= j - i.
   • If either condition is satisfied, increment the ans counter.

5. Return the Result: After all possible indices are evaluated, ans contains the total number of beautiful splits.

By precomputing the LCP, the solution efficiently checks the prefix conditions needed to determine beautiful splits, ensuring that the algorithm runs efficiently even for larger input sizes.

Example Walkthrough

Let's walk through a simple example using the solution approach described above. Consider the array nums = [1, 2, 1, 2, 1].

1. Initialize LCP Table:

   • We'll create a 5 x 5 lcp table initialized with zeros, as our array length n = 5.

2. Build LCP Table:

   • Starting from the end of the array:
     • Compare nums[4] and nums[3]. They are different, so lcp[4][3] = 0.
     • Compare nums[3] and nums[2]. They are the same, so lcp[3][2] = lcp[4][3] + 1 = 1.
     • Continue filling the table for other pairs in a similar fashion.
   • The completed LCP table might look something like this (this is illustrative):

     lcp = [
       [2, 0, 2, 0, 1],
       [0, 2, 0, 1, 0],
       [0, 0, 1, 0, 0],
       [0, 0, 0, 1, 0],
       [0, 0, 0, 0, 0]
     ]

3. Enumerate Possible Splits:

   • Let's iterate over possible indices i and j:
     • For example, set i = 1 and j = 3.

4. Check Beautiful Split Condition:

   • Check if nums1 is a prefix of nums2:
     • For i = 1, j = 3, we need lcp[0][1] >= 1 and 1 <= 3 - 1.
   • Alternatively, check if nums2 is a prefix of nums3:
     • For i = 1, j = 3, check if lcp[1][3] >= 3 - 1.
   • If either holds, the split is beautiful. Count this in ans.

5. Return the Result:

   • Continue checking other pairs (i, j). After evaluating all, return ans which holds the count of beautiful splits.

This example illustrates how you construct and utilize the LCP table to efficiently find beautiful splits within the given constraints.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n^2). This complexity arises from the nested loops used to fill the lcp array and to compute the final result. Specifically, the loop that creates the longest common prefix (LCP) array iterates over all pairs (i, j) with i < j, leading to a quadratic number of iterations. Further loops process these results with similar complexity.

The space complexity of the code is O(n^2). This is due to the creation of the LCP table lcp, which is a 2D list of size (n+1) x (n+1), storing values for each pair of indices in the input list nums.

Learn more about how to find time and space complexity quickly.