README_EN.md

comments	difficulty	edit_url	rating	source	tags
true	Medium	https://github.com/doocs/leetcode/edit/main/solution/3300-3399/3388.Count%20Beautiful%20Splits%20in%20an%20Array/README_EN.md	2364	Weekly Contest 428 Q3	Array Dynamic Programming

3388. Count Beautiful Splits in an Array

中文文档

Description

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

Solutions

Solution 1: LCP + Enumeration

We can preprocess $\text{LCP}[i][j]$ to represent the length of the longest common prefix of $\textit{nums}[i:]$ and $\textit{nums}[j:]$. Initially, $\text{LCP}[i][j] = 0$.

Next, we enumerate $i$ and $j$ in reverse order. For each pair of $i$ and $j$, if $\textit{nums}[i] = \textit{nums}[j]$, then we can get $\text{LCP}[i][j] = \text{LCP}[i + 1][j + 1] + 1$.

Finally, we enumerate the ending position $i$ of the first subarray (excluding position $i$) and the ending position $j$ of the second subarray (excluding position $j$). The length of the first subarray is $i$, the length of the second subarray is $j - i$, and the length of the third subarray is $n - j$. If $i \leq j - i$ and $\text{LCP}[0][i] \geq i$, or $j - i \leq n - j$ and $\text{LCP}[i][j] \geq j - i$, then this split is beautiful, and we increment the answer by one.

After enumerating, the answer is the number of beautiful splits.

The time complexity is $O(n^2)$, and the space complexity is $O(n^2)$. Here, $n$ is the length of the array $\textit{nums}$.

Python3

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

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;
    }
}

C++

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;
    }
};

Go

func beautifulSplits(nums []int) (ans int) {
    n := len(nums)
    lcp := make([][]int, n+1)
    for i := range lcp {
        lcp[i] = make([]int, n+1)
    }

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

    for i := 1; i < n-1; i++ {
        for j := i + 1; j < n; j++ {
            a := i <= j-i && lcp[0][i] >= i
            b := j-i <= n-j && lcp[i][j] >= j-i
            if a || b {
                ans++
            }
        }
    }

    return
}

TypeScript

function beautifulSplits(nums: number[]): number {
    const n = nums.length;
    const lcp: number[][] = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));

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

    let ans = 0;
    for (let i = 1; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            const a = i <= j - i && lcp[0][i] >= i;
            const b = j - i <= n - j && lcp[i][j] >= j - i;
            if (a || b) {
                ans++;
            }
        }
    }

    return ans;
}