bowang0911/leetcode huggingface dataset:
Move Sub-Tree of N-Ary Tree

Given the `root` of an N-ary tree of unique values, and two nodes of the tree `p` and `q`.

You should move the subtree of the node `p` to become a direct child of node `q`. If `p` is already a direct child of `q`, do not change anything. Node `p` **must be** the last child in the children list of node `q`.

Return _the root of the tree_ after adjusting it.

There are 3 cases for nodes `p` and `q`:

1.  Node `q` is in the sub-tree of node `p`.
2.  Node `p` is in the sub-tree of node `q`.
3.  Neither node `p` is in the sub-tree of node `q` nor node `q` is in the sub-tree of node `p`.

In cases 2 and 3, you just need to move `p` (with its sub-tree) to be a child of `q`, but in case 1 the tree may be disconnected, thus you need to reconnect the tree again. **Please read the examples carefully before solving this problem.**

_Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples)._

For example, the above tree is serialized as `[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]`.

**Example 1:**

**Input:** root = \[1,null,2,3,null,4,5,null,6,null,7,8\], p = 4, q = 1
**Output:** \[1,null,2,3,4,null,5,null,6,null,7,8\]
**Explanation:** This example follows the second case as node p is in the sub-tree of node q. We move node p with its sub-tree to be a direct child of node q.
Notice that node 4 is the last child of node 1.

**Example 2:**

**Input:** root = \[1,null,2,3,null,4,5,null,6,null,7,8\], p = 7, q = 4
**Output:** \[1,null,2,3,null,4,5,null,6,null,7,8\]
**Explanation:** Node 7 is already a direct child of node 4. We don't change anything.

**Example 3:**

**Input:** root = \[1,null,2,3,null,4,5,null,6,null,7,8\], p = 3, q = 8
**Output:** \[1,null,2,null,4,5,null,7,8,null,null,null,3,null,6\]
**Explanation:** This example follows case 3 because node p is not in the sub-tree of node q and vice-versa. We can move node 3 with its sub-tree and make it as node 8's child.

**Constraints:**

*   The total number of nodes is between `[2, 1000]`.
*   Each node has a **unique** value.
*   `p != null`
*   `q != null`
*   `p` and `q` are two different nodes (i.e. `p != q`).
Water Bottles

There are `numBottles` water bottles that are initially full of water. You can exchange `numExchange` empty water bottles from the market with one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Given the two integers `numBottles` and `numExchange`, return _the **maximum** number of water bottles you can drink_.

**Example 1:**

**Input:** numBottles = 9, numExchange = 3
**Output:** 13
**Explanation:** You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

**Example 2:**

**Input:** numBottles = 15, numExchange = 4
**Output:** 19
**Explanation:** You can exchange 4 empty bottles to get 1 full water bottle. 
Number of water bottles you can drink: 15 + 3 + 1 = 19.

**Constraints:**

*   `1 <= numBottles <= 100`
*   `2 <= numExchange <= 100`
Number of Nodes in the Sub-Tree With the Same Label

You are given a tree (i.e. a connected, undirected graph that has no cycles) consisting of `n` nodes numbered from `0` to `n - 1` and exactly `n - 1` `edges`. The **root** of the tree is the node `0`, and each node of the tree has **a label** which is a lower-case character given in the string `labels` (i.e. The node with the number `i` has the label `labels[i]`).

The `edges` array is given on the form `edges[i] = [ai, bi]`, which means there is an edge between nodes `ai` and `bi` in the tree.

Return _an array of size `n`_ where `ans[i]` is the number of nodes in the subtree of the `ith` node which have the same label as node `i`.

A subtree of a tree `T` is the tree consisting of a node in `T` and all of its descendant nodes.

**Example 1:**

**Input:** n = 7, edges = \[\[0,1\],\[0,2\],\[1,4\],\[1,5\],\[2,3\],\[2,6\]\], labels =  "abaedcd "
**Output:** \[2,1,1,1,1,1,1\]
**Explanation:** Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

**Example 2:**

**Input:** n = 4, edges = \[\[0,1\],\[1,2\],\[0,3\]\], labels =  "bbbb "
**Output:** \[4,2,1,1\]
**Explanation:** The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.

**Example 3:**

**Input:** n = 5, edges = \[\[0,1\],\[0,2\],\[1,3\],\[0,4\]\], labels =  "aabab "
**Output:** \[3,2,1,1,1\]

**Constraints:**

*   `1 <= n <= 105`
*   `edges.length == n - 1`
*   `edges[i].length == 2`
*   `0 <= ai, bi < n`
*   `ai != bi`
*   `labels.length == n`
*   `labels` is consisting of only of lowercase English letters.
Maximum Number of Non-Overlapping Substrings

Given a string `s` of lowercase letters, you need to find the maximum number of **non-empty** substrings of `s` that meet the following conditions:

1.  The substrings do not overlap, that is for any two substrings `s[i..j]` and `s[x..y]`, either `j < x` or `i > y` is true.
2.  A substring that contains a certain character `c` must also contain all occurrences of `c`.

Find _the maximum number of substrings that meet the above conditions_. If there are multiple solutions with the same number of substrings, _return the one with minimum total length._ It can be shown that there exists a unique solution of minimum total length.

Notice that you can return the substrings in **any** order.

**Example 1:**

**Input:** s =  "adefaddaccc "
**Output:** \[ "e ", "f ", "ccc "\]
**Explanation:** The following are all the possible substrings that meet the conditions:
\[
   "adefaddaccc "
   "adefadda ",
   "ef ",
   "e ",
   "f ",
   "ccc ",
\]
If we choose the first string, we cannot choose anything else and we'd get only 1. If we choose  "adefadda ", we are left with  "ccc " which is the only one that doesn't overlap, thus obtaining 2 substrings. Notice also, that it's not optimal to choose  "ef " since it can be split into two. Therefore, the optimal way is to choose \[ "e ", "f ", "ccc "\] which gives us 3 substrings. No other solution of the same number of substrings exist.

**Example 2:**

**Input:** s =  "abbaccd "
**Output:** \[ "d ", "bb ", "cc "\]
**Explanation:** Notice that while the set of substrings \[ "d ", "abba ", "cc "\] also has length 3, it's considered incorrect since it has larger total length.

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` contains only lowercase English letters.
Find a Value of a Mysterious Function Closest to Target

Winston was given the above mysterious function `func`. He has an integer array `arr` and an integer `target` and he wants to find the values `l` and `r` that make the value `|func(arr, l, r) - target|` minimum possible.

Return _the minimum possible value_ of `|func(arr, l, r) - target|`.

Notice that `func` should be called with the values `l` and `r` where `0 <= l, r < arr.length`.

**Example 1:**

**Input:** arr = \[9,12,3,7,15\], target = 5
**Output:** 2
**Explanation:** Calling func with all the pairs of \[l,r\] = \[\[0,0\],\[1,1\],\[2,2\],\[3,3\],\[4,4\],\[0,1\],\[1,2\],\[2,3\],\[3,4\],\[0,2\],\[1,3\],\[2,4\],\[0,3\],\[1,4\],\[0,4\]\], Winston got the following results \[9,12,3,7,15,8,0,3,7,0,0,3,0,0,0\]. The value closest to 5 is 7 and 3, thus the minimum difference is 2.

**Example 2:**

**Input:** arr = \[1000000,1000000,1000000\], target = 1
**Output:** 999999
**Explanation:** Winston called the func with all possible values of \[l,r\] and he always got 1000000, thus the min difference is 999999.

**Example 3:**

**Input:** arr = \[1,2,4,8,16\], target = 0
**Output:** 0

**Constraints:**

*   `1 <= arr.length <= 105`
*   `1 <= arr[i] <= 106`
*   `0 <= target <= 107`
Diameter of N-Ary Tree

Given a `root` of an [N-ary tree](https://leetcode.com/articles/introduction-to-n-ary-trees/), you need to compute the length of the diameter of the tree.

The diameter of an N-ary tree is the length of the **longest** path between any two nodes in the tree. This path may or may not pass through the root.

(_Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.)_

**Example 1:**

**Input:** root = \[1,null,3,2,4,null,5,6\]
**Output:** 3
**Explanation:** Diameter is shown in red color.

**Example 2:**

**Input:** root = \[1,null,2,null,3,4,null,5,null,6\]
**Output:** 4

**Example 3:**

**Input:** root = \[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14\]
**Output:** 7

**Constraints:**

*   The depth of the n-ary tree is less than or equal to `1000`.
*   The total number of nodes is between `[1, 104]`.
Count Odd Numbers in an Interval Range

Given two non-negative integers `low` and `high`. Return the _count of odd numbers between_ `low` _and_ `high` _(inclusive)_.

**Example 1:**

**Input:** low = 3, high = 7
**Output:** 3
**Explanation:** The odd numbers between 3 and 7 are \[3,5,7\].

**Example 2:**

**Input:** low = 8, high = 10
**Output:** 1
**Explanation:** The odd numbers between 8 and 10 are \[9\].

**Constraints:**

*   `0 <= low <= high <= 10^9`
Number of Sub-arrays With Odd Sum

Given an array of integers `arr`, return _the number of subarrays with an **odd** sum_.

Since the answer can be very large, return it modulo `109 + 7`.

**Example 1:**

**Input:** arr = \[1,3,5\]
**Output:** 4
**Explanation:** All subarrays are \[\[1\],\[1,3\],\[1,3,5\],\[3\],\[3,5\],\[5\]\]
All sub-arrays sum are \[1,4,9,3,8,5\].
Odd sums are \[1,9,3,5\] so the answer is 4.

**Example 2:**

**Input:** arr = \[2,4,6\]
**Output:** 0
**Explanation:** All subarrays are \[\[2\],\[2,4\],\[2,4,6\],\[4\],\[4,6\],\[6\]\]
All sub-arrays sum are \[2,6,12,4,10,6\].
All sub-arrays have even sum and the answer is 0.

**Example 3:**

**Input:** arr = \[1,2,3,4,5,6,7\]
**Output:** 16

**Constraints:**

*   `1 <= arr.length <= 105`
*   `1 <= arr[i] <= 100`
Number of Good Ways to Split a String

You are given a string `s`.

A split is called **good** if you can split `s` into two non-empty strings `sleft` and `sright` where their concatenation is equal to `s` (i.e., `sleft + sright = s`) and the number of distinct letters in `sleft` and `sright` is the same.

Return _the number of **good splits** you can make in `s`_.

**Example 1:**

**Input:** s =  "aacaba "
**Output:** 2
**Explanation:** There are 5 ways to split ` "aacaba "` and 2 of them are good. 
( "a ",  "acaba ") Left string and right string contains 1 and 3 different letters respectively.
( "aa ",  "caba ") Left string and right string contains 1 and 3 different letters respectively.
( "aac ",  "aba ") Left string and right string contains 2 and 2 different letters respectively (good split).
( "aaca ",  "ba ") Left string and right string contains 2 and 2 different letters respectively (good split).
( "aacab ",  "a ") Left string and right string contains 3 and 1 different letters respectively.

**Example 2:**

**Input:** s =  "abcd "
**Output:** 1
**Explanation:** Split the string as follows ( "ab ",  "cd ").

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists of only lowercase English letters.
Minimum Number of Increments on Subarrays to Form a Target Array

You are given an integer array `target`. You have an integer array `initial` of the same size as `target` with all elements initially zeros.

In one operation you can choose **any** subarray from `initial` and increment each value by one.

Return _the minimum number of operations to form a_ `target` _array from_ `initial`.

The test cases are generated so that the answer fits in a 32-bit integer.

**Example 1:**

**Input:** target = \[1,2,3,2,1\]
**Output:** 3
**Explanation:** We need at least 3 operations to form the target array from the initial array.
\[**0,0,0,0,0**\] increment 1 from index 0 to 4 (inclusive).
\[1,**1,1,1**,1\] increment 1 from index 1 to 3 (inclusive).
\[1,2,**2**,2,1\] increment 1 at index 2.
\[1,2,3,2,1\] target array is formed.

**Example 2:**

**Input:** target = \[3,1,1,2\]
**Output:** 4
**Explanation:** \[**0,0,0,0**\] -> \[1,1,1,**1**\] -> \[**1**,1,1,2\] -> \[**2**,1,1,2\] -> \[3,1,1,2\]

**Example 3:**

**Input:** target = \[3,1,5,4,2\]
**Output:** 7
**Explanation:** \[**0,0,0,0,0**\] -> \[**1**,1,1,1,1\] -> \[**2**,1,1,1,1\] -> \[3,1,**1,1,1**\] -> \[3,1,**2,2**,2\] -> \[3,1,**3,3**,2\] -> \[3,1,**4**,4,2\] -> \[3,1,5,4,2\].

**Constraints:**

*   `1 <= target.length <= 105`
*   `1 <= target[i] <= 105`
Shuffle String

You are given a string `s` and an integer array `indices` of the **same length**. The string `s` will be shuffled such that the character at the `ith` position moves to `indices[i]` in the shuffled string.

Return _the shuffled string_.

**Example 1:**

**Input:** s =  "codeleet ", `indices` = \[4,5,6,7,0,2,1,3\]
**Output:**  "leetcode "
**Explanation:** As shown,  "codeleet " becomes  "leetcode " after shuffling.

**Example 2:**

**Input:** s =  "abc ", `indices` = \[0,1,2\]
**Output:**  "abc "
**Explanation:** After shuffling, each character remains in its position.

**Constraints:**

*   `s.length == indices.length == n`
*   `1 <= n <= 100`
*   `s` consists of only lowercase English letters.
*   `0 <= indices[i] < n`
*   All values of `indices` are **unique**.
Minimum Suffix Flips

You are given a **0-indexed** binary string `target` of length `n`. You have another binary string `s` of length `n` that is initially set to all zeros. You want to make `s` equal to `target`.

In one operation, you can pick an index `i` where `0 <= i < n` and flip all bits in the **inclusive** range `[i, n - 1]`. Flip means changing `'0'` to `'1'` and `'1'` to `'0'`.

Return _the minimum number of operations needed to make_ `s` _equal to_ `target`.

**Example 1:**

**Input:** target =  "10111 "
**Output:** 3
**Explanation:** Initially, s =  "00000 ".
Choose index i = 2:  "00000 " ->  "00111 "
Choose index i = 0:  "00111 " ->  "11000 "
Choose index i = 1:  "11000 " ->  "10111 "
We need at least 3 flip operations to form target.

**Example 2:**

**Input:** target =  "101 "
**Output:** 3
**Explanation:** Initially, s =  "000 ".
Choose index i = 0:  "000 " ->  "111 "
Choose index i = 1:  "111 " ->  "100 "
Choose index i = 2:  "100 " ->  "101 "
We need at least 3 flip operations to form target.

**Example 3:**

**Input:** target =  "00000 "
**Output:** 0
**Explanation:** We do not need any operations since the initial s already equals target.

**Constraints:**

*   `n == target.length`
*   `1 <= n <= 105`
*   `target[i]` is either `'0'` or `'1'`.
Number of Good Leaf Nodes Pairs

You are given the `root` of a binary tree and an integer `distance`. A pair of two different **leaf** nodes of a binary tree is said to be good if the length of **the shortest path** between them is less than or equal to `distance`.

Return _the number of good leaf node pairs_ in the tree.

**Example 1:**

**Input:** root = \[1,2,3,null,4\], distance = 3
**Output:** 1
**Explanation:** The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

**Example 2:**

**Input:** root = \[1,2,3,4,5,6,7\], distance = 3
**Output:** 2
**Explanation:** The good pairs are \[4,5\] and \[6,7\] with shortest path = 2. The pair \[4,6\] is not good because the length of ther shortest path between them is 4.

**Example 3:**

**Input:** root = \[7,1,4,6,null,5,3,null,null,null,null,null,2\], distance = 3
**Output:** 1
**Explanation:** The only good pair is \[2,5\].

**Constraints:**

*   The number of nodes in the `tree` is in the range `[1, 210].`
*   `1 <= Node.val <= 100`
*   `1 <= distance <= 10`
String Compression II

[Run-length encoding](http://en.wikipedia.org/wiki/Run-length_encoding) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string `"aabccc "` we replace `"aa "` by `"a2 "` and replace `"ccc "` by `"c3 "`. Thus the compressed string becomes `"a2bc3 "`.

Notice that in this problem, we are not adding `'1'` after single characters.

Given a string `s` and an integer `k`. You need to delete **at most** `k` characters from `s` such that the run-length encoded version of `s` has minimum length.

Find the _minimum length of the run-length encoded version of_ `s` _after deleting at most_ `k` _characters_.

**Example 1:**

**Input:** s =  "aaabcccd ", k = 2
**Output:** 4
**Explanation:** Compressing s without deleting anything will give us  "a3bc3d " of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s =  "abcccd " which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be  "a3c3 " of length 4.

**Example 2:**

**Input:** s =  "aabbaa ", k = 2
**Output:** 2
**Explanation:** If we delete both 'b' characters, the resulting compressed string would be  "a4 " of length 2.

**Example 3:**

**Input:** s =  "aaaaaaaaaaa ", k = 0
**Output:** 3
**Explanation:** Since k is zero, we cannot delete anything. The compressed string is  "a11 " of length 3.

**Constraints:**

*   `1 <= s.length <= 100`
*   `0 <= k <= s.length`
*   `s` contains only lowercase English letters.
Find the Index of the Large Integer

We have an integer array `arr`, where all the integers in `arr` are equal except for one integer which is **larger** than the rest of the integers. You will not be given direct access to the array, instead, you will have an **API** `ArrayReader` which have the following functions:

*   `int compareSub(int l, int r, int x, int y)`: where `0 <= l, r, x, y < ArrayReader.length()`, `l <= r and` `x <= y`. The function compares the sum of sub-array `arr[l..r]` with the sum of the sub-array `arr[x..y]` and returns:
    *   **1** if `arr[l]+arr[l+1]+...+arr[r] > arr[x]+arr[x+1]+...+arr[y]`.
    *   **0** if `arr[l]+arr[l+1]+...+arr[r] == arr[x]+arr[x+1]+...+arr[y]`.
    *   **\-1** if `arr[l]+arr[l+1]+...+arr[r] < arr[x]+arr[x+1]+...+arr[y]`.
*   `int length()`: Returns the size of the array.

You are allowed to call `compareSub()` **20 times** at most. You can assume both functions work in `O(1)` time.

Return _the index of the array `arr` which has the largest integer_.

**Example 1:**

**Input:** arr = \[7,7,7,7,10,7,7,7\]
**Output:** 4
**Explanation:** The following calls to the API
reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr\[0\] with arr\[1\]).
Thus we know that arr\[0\] and arr\[1\] doesn't contain the largest element.
reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr\[2\] and arr\[3\].
reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr\[4\] is the largest element in the array.
Notice that we made only 3 calls, so the answer is valid.

**Example 2:**

**Input:** nums = \[6,6,12\]
**Output:** 2

**Constraints:**

*   `2 <= arr.length <= 5 * 105`
*   `1 <= arr[i] <= 100`
*   All elements of `arr` are equal except for one element which is larger than all other elements.

**Follow up:**

*   What if there are two numbers in `arr` that are bigger than all other numbers?
*   What if there is one number that is bigger than other numbers and one number that is smaller than other numbers?
Count Good Triplets

Given an array of integers `arr`, and three integers `a`, `b` and `c`. You need to find the number of good triplets.

A triplet `(arr[i], arr[j], arr[k])` is **good** if the following conditions are true:

*   `0 <= i < j < k < arr.length`
*   `|arr[i] - arr[j]| <= a`
*   `|arr[j] - arr[k]| <= b`
*   `|arr[i] - arr[k]| <= c`

Where `|x|` denotes the absolute value of `x`.

Return _the number of good triplets_.

**Example 1:**

**Input:** arr = \[3,0,1,1,9,7\], a = 7, b = 2, c = 3
**Output:** 4
**Explanation:** There are 4 good triplets: \[(3,0,1), (3,0,1), (3,1,1), (0,1,1)\].

**Example 2:**

**Input:** arr = \[1,1,2,2,3\], a = 0, b = 0, c = 1
**Output:** 0
**Explanation:** No triplet satisfies all conditions.

**Constraints:**

*   `3 <= arr.length <= 100`
*   `0 <= arr[i] <= 1000`
*   `0 <= a, b, c <= 1000`
Find the Winner of an Array Game

Given an integer array `arr` of **distinct** integers and an integer `k`.

A game will be played between the first two elements of the array (i.e. `arr[0]` and `arr[1]`). In each round of the game, we compare `arr[0]` with `arr[1]`, the larger integer wins and remains at position `0`, and the smaller integer moves to the end of the array. The game ends when an integer wins `k` consecutive rounds.

Return _the integer which will win the game_.

It is **guaranteed** that there will be a winner of the game.

**Example 1:**

**Input:** arr = \[2,1,3,5,4,6,7\], k = 2
**Output:** 5
**Explanation:** Let's see the rounds of the game:
Round |       arr       | winner | win\_count
  1   | \[2,1,3,5,4,6,7\] | 2      | 1
  2   | \[2,3,5,4,6,7,1\] | 3      | 1
  3   | \[3,5,4,6,7,1,2\] | 5      | 1
  4   | \[5,4,6,7,1,2,3\] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

**Example 2:**

**Input:** arr = \[3,2,1\], k = 10
**Output:** 3
**Explanation:** 3 will win the first 10 rounds consecutively.

**Constraints:**

*   `2 <= arr.length <= 105`
*   `1 <= arr[i] <= 106`
*   `arr` contains **distinct** integers.
*   `1 <= k <= 109`
Minimum Swaps to Arrange a Binary Grid

Given an `n x n` binary `grid`, in one step you can choose two **adjacent rows** of the grid and swap them.

A grid is said to be **valid** if all the cells above the main diagonal are **zeros**.

Return _the minimum number of steps_ needed to make the grid valid, or **\-1** if the grid cannot be valid.

The main diagonal of a grid is the diagonal that starts at cell `(1, 1)` and ends at cell `(n, n)`.

**Example 1:**

**Input:** grid = \[\[0,0,1\],\[1,1,0\],\[1,0,0\]\]
**Output:** 3

**Example 2:**

**Input:** grid = \[\[0,1,1,0\],\[0,1,1,0\],\[0,1,1,0\],\[0,1,1,0\]\]
**Output:** -1
**Explanation:** All rows are similar, swaps have no effect on the grid.

**Example 3:**

**Input:** grid = \[\[1,0,0\],\[1,1,0\],\[1,1,1\]\]
**Output:** 0

**Constraints:**

*   `n == grid.length` `== grid[i].length`
*   `1 <= n <= 200`
*   `grid[i][j]` is either `0` or `1`
Get the Maximum Score

You are given two **sorted** arrays of distinct integers `nums1` and `nums2.`

A **valid path** is defined as follows:

*   Choose array `nums1` or `nums2` to traverse (from index-0).
*   Traverse the current array from left to right.
*   If you are reading any value that is present in `nums1` and `nums2` you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

The **score** is defined as the sum of uniques values in a valid path.

Return _the maximum score you can obtain of all possible **valid paths**_. Since the answer may be too large, return it modulo `109 + 7`.

**Example 1:**

**Input:** nums1 = \[2,4,5,8,10\], nums2 = \[4,6,8,9\]
**Output:** 30
**Explanation:** Valid paths:
\[2,4,5,8,10\], \[2,4,5,8,9\], \[2,4,6,8,9\], \[2,4,6,8,10\],  (starting from nums1)
\[4,6,8,9\], \[4,5,8,10\], \[4,5,8,9\], \[4,6,8,10\]    (starting from nums2)
The maximum is obtained with the path in green **\[2,4,6,8,10\]**.

**Example 2:**

**Input:** nums1 = \[1,3,5,7,9\], nums2 = \[3,5,100\]
**Output:** 109
**Explanation:** Maximum sum is obtained with the path **\[1,3,5,100\]**.

**Example 3:**

**Input:** nums1 = \[1,2,3,4,5\], nums2 = \[6,7,8,9,10\]
**Output:** 40
**Explanation:** There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path \[6,7,8,9,10\].

**Constraints:**

*   `1 <= nums1.length, nums2.length <= 105`
*   `1 <= nums1[i], nums2[i] <= 107`
*   `nums1` and `nums2` are strictly increasing.