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 nums2ORnums2 is a prefix of nums3.
Return the number of ways you can make this split.
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.
classSolution {
publicintcountBeautifulSplits(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
classSolution {
funcountBeautifulSplits(nums: IntArray): Int {
val n = nums.size
var ans = 0for (i in1 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
classSolution:
defcountBeautifulSplits(self, nums: list[int]) -> int:
n = len(nums)
ans =0for 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 +=1return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
impl Solution {
pubfncount_beautiful_splits(nums: Vec<i32>) -> i32 {
let n = nums.len();
letmut ans =0;
for i in1..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
}
}