Split and Merge Array Transformation
You are given two integer arrays nums1 and nums2, each of length n. You may perform the following split-and-merge operation on nums1 any number of times:
- Choose a subarray
nums1[L..R]. - Remove that subarray, leaving the prefix
nums1[0..L-1](empty ifL = 0) and the suffixnums1[R+1..n-1](empty ifR = n - 1). - Re-insert the removed subarray, in its original order, at any position in the remaining array: between any two elements, at the very start, or at the very end.
Return the minimum number of split-and-merge operations needed to transform nums1 into nums2.
Example 1
Input
nums1 = [3,1,2], nums2 = [1,2,3]Output
1Splitting out
[3] and inserting it at the end transforms [3,1,2] into [1,2,3] in one operation.Example 2
Input
nums1 = [1,1,2,3,4,5], nums2 = [5,4,3,2,1,1]Output
3The stated sequence of three split-and-merge operations transforms
nums1 into nums2, and this is the minimum possible.Constraints
- 2 <= n == nums1.length == nums2.length <= 6
- -10^5 <= nums1[i], nums2[i] <= 10^5
- nums2 is a permutation of nums1.