| <span id="1521">1521</span> | [Find a Value of a Mysterious Function Closest to Target](https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target "找到最接近目标值的函数值") | [Go](problems/find-a-value-of-a-mysterious-function-closest-to-target) | Hard |

| <span id="1520">1520</span> | [Maximum Number of Non-Overlapping Substrings](https://leetcode.com/problems/maximum-number-of-non-overlapping-substrings "最多的不重叠子字符串") | [Go](problems/maximum-number-of-non-overlapping-substrings) | Medium |

| <span id="1519">1519</span> | [Number of Nodes in the Sub-Tree With the Same Label](https://leetcode.com/problems/number-of-nodes-in-the-sub-tree-with-the-same-label "子树中标签相同的节点数") | [Go](problems/number-of-nodes-in-the-sub-tree-with-the-same-label) | Medium |

| <span id="1518">1518</span> | [Water Bottles](https://leetcode.com/problems/water-bottles "换酒问题") | [Go](problems/water-bottles) | Easy |

| <span id="1517">1517</span> | [Find Users With Valid E-Mails](https://leetcode.com/problems/find-users-with-valid-e-mails) 🔒 | [MySQL](problems/find-users-with-valid-e-mails) | Easy |

| <span id="1516">1516</span> | [Move Sub-Tree of N-Ary Tree](https://leetcode.com/problems/move-sub-tree-of-n-ary-tree) 🔒 | [Go](problems/move-sub-tree-of-n-ary-tree) | Hard |

[< Previous](../maximum-number-of-non-overlapping-substrings "Maximum Number of Non-Overlapping Substrings")

　　　　　　　　　　　　　　　　

Next >

<p><img alt="" src="https://assets.leetcode.com/uploads/2020/07/09/change.png" style="width: 635px; height: 312px;" /></p>

<p>Winston was given the above mysterious function <code>func</code>. He has an integer array <code>arr</code> and an integer <code>target</code> and he wants to find the values&nbsp;<code>l</code> and <code>r</code>&nbsp;that make&nbsp;the value <code>|func(arr, l, r) - target|</code> minimum possible.</p>

<p>Return <em>the minimum possible value</em> of <code>|func(arr, l, r) - target|</code>.</p>

<p>Notice that <code>func</code> should be called with the values&nbsp;<code>l</code> and <code>r</code> where <code>0 &lt;= l, r &lt; arr.length</code>.</p>

<p>&nbsp;</p>

<p><strong>Example 1:</strong></p>

<pre>

<strong>Input:</strong> arr = [9,12,3,7,15], target = 5

<strong>Output:</strong> 2

<strong>Explanation:</strong> 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.

</pre>

<p><strong>Example 2:</strong></p>

<pre>

<strong>Input:</strong> arr = [1000000,1000000,1000000], target = 1

<strong>Output:</strong> 999999

<strong>Explanation:</strong> Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.

</pre>

<p><strong>Example 3:</strong></p>

<pre>

<strong>Input:</strong> arr = [1,2,4,8,16], target = 0

<strong>Output:</strong> 0

</pre>

<p>&nbsp;</p>

<p><strong>Constraints:</strong></p>

<ul>

<li><code>1 &lt;= arr.length &lt;= 10^5</code></li>

<li><code>1 &lt;= arr[i] &lt;= 10^6</code></li>

<li><code>0 &lt;= target &lt;= 10^7</code></li>

</ul>

[[Bit Manipulation](../../tag/bit-manipulation/README.md)]

[[Segment Tree](../../tag/segment-tree/README.md)]

[[Binary Search](../../tag/binary-search/README.md)]

<details>

<summary>Hint 1</summary>

If the and value of sub-array arr[i...j] is ≥ the and value of the sub-array arr[i...j+1].

</details>

<details>

<summary>Hint 2</summary>

For each index i using binary search or ternary search find the index j where |target - AND(arr[i...j])| is minimum, minimize this value with the global answer.

</details>

[< Previous](../move-sub-tree-of-n-ary-tree "Move Sub-Tree of N-Ary Tree")

　　　　　　　　　　　　　　　　

[Next >](../water-bottles "Water Bottles")

Create table If Not Exists Users (user_id int, name varchar(30), mail varchar(50));

Truncate table Users;

insert into Users (user_id, name, mail) values ('1', 'Winston', 'winston@leetcode.com');

insert into Users (user_id, name, mail) values ('2', 'Jonathan', 'jonathanisgreat');

insert into Users (user_id, name, mail) values ('3', 'Annabelle', 'bella-@leetcode.com');

insert into Users (user_id, name, mail) values ('4', 'Sally', 'sally.come@leetcode.com');

insert into Users (user_id, name, mail) values ('5', 'Marwan', 'quarz#2020@leetcode.com');

insert into Users (user_id, name, mail) values ('6', 'David', 'david69@gmail.com');

insert into Users (user_id, name, mail) values ('7', 'Shapiro', '.shapo@leetcode.com');

[< Previous](../number-of-nodes-in-the-sub-tree-with-the-same-label "Number of Nodes in the Sub-Tree With the Same Label")

　　　　　　　　　　　　　　　　

[Next >](../find-a-value-of-a-mysterious-function-closest-to-target "Find a Value of a Mysterious Function Closest to Target")

<p>Given a string <code>s</code>&nbsp;of lowercase letters, you need to find the maximum number of <strong>non-empty</strong> substrings of&nbsp;<code>s</code>&nbsp;that meet the following conditions:</p>

<ol>

<li>The substrings do not overlap, that is for any two substrings <code>s[i..j]</code> and <code>s[k..l]</code>, either <code>j &lt; k</code> or <code>i &gt; l</code>&nbsp;is true.</li>

<li>A substring that contains a certain character&nbsp;<code>c</code>&nbsp;must also contain all occurrences of <code>c</code>.</li>

</ol>

<p>Find <em>the maximum number of substrings that meet the above conditions</em>. If there are multiple solutions with the same number of substrings, <em>return the one with minimum total length.&nbsp;</em>It can be shown that there exists a unique solution of minimum total length.</p>

<p>Notice that you can return the substrings in <strong>any</strong> order.</p>

<p>&nbsp;</p>

<p><strong>Example 1:</strong></p>

<pre>

<strong>Input:</strong> s = &quot;adefaddaccc&quot;

<strong>Output:</strong> [&quot;e&quot;,&quot;f&quot;,&quot;ccc&quot;]

<b>Explanation:</b>&nbsp;The following are all the possible substrings that meet the conditions:

[

&nbsp; &quot;adefaddaccc&quot;

&nbsp; &quot;adefadda&quot;,

&nbsp; &quot;ef&quot;,

&nbsp; &quot;e&quot;,

&quot;f&quot;,

&nbsp; &quot;ccc&quot;,

]

If we choose the first string, we cannot choose anything else and we&#39;d get only 1. If we choose &quot;adefadda&quot;, we are left with &quot;ccc&quot; which is the only one that doesn&#39;t overlap, thus obtaining 2 substrings. Notice also, that it&#39;s not optimal to choose &quot;ef&quot; since it can be split into two. Therefore, the optimal way is to choose [&quot;e&quot;,&quot;f&quot;,&quot;ccc&quot;] which gives us 3 substrings. No other solution of the same number of substrings exist.

</pre>

<p><strong>Example 2:</strong></p>

<pre>

<strong>Input:</strong> s = &quot;abbaccd&quot;

<strong>Output:</strong> [&quot;d&quot;,&quot;bb&quot;,&quot;cc&quot;]

<b>Explanation: </b>Notice that while the set of substrings [&quot;d&quot;,&quot;abba&quot;,&quot;cc&quot;] also has length 3, it&#39;s considered incorrect since it has larger total length.

</pre>

<p>&nbsp;</p>

<p><strong>Constraints:</strong></p>

<ul>

<li><code>1 &lt;= s.length &lt;= 10^5</code></li>

<li><code>s</code>&nbsp;contains only lowercase English letters.</li>

</ul>

[[Greedy](../../tag/greedy/README.md)]

<details>

<summary>Hint 1</summary>

Notice that it's impossible for any two valid substrings to overlap unless one is inside another.

</details>

<details>

<summary>Hint 2</summary>

We can start by finding the starting and ending index for each character.

</details>

<details>

<summary>Hint 3</summary>

From these indices, we can form the substrings by expanding each character's range if necessary (if another character exists in the range with smaller/larger starting/ending index).

</details>

<details>

<summary>Hint 4</summary>

Sort the valid substrings by length and greedily take those with the smallest length, discarding the ones that overlap those we took.

</details>

<p>Given a binary tree, write a function to get the maximum width of the given tree. The maximum width of a tree is the maximum width among all levels.</p>

<p>It is <strong>guaranteed</strong> that the answer will in the range of 32-bit signed integer.</p>

<p>&nbsp;</p>

<p><strong>Constraints:</strong></p>

<ul>

<li>The&nbsp;given binary tree will have between&nbsp;<code>1</code>&nbsp;and&nbsp;<code>3000</code>&nbsp;nodes.</li>

</ul>

[< Previous](../best-position-for-a-service-centre "Best Position for a Service Centre")

　　　　　　　　　　　　　　　　

[Next >](../find-users-with-valid-e-mails "Find Users With Valid E-Mails")

[[Tree](../../tag/tree/README.md)]

<details>

<summary>Hint 1</summary>

Disconnect node p from its parent and append it to the children list of node q.

</details>

<details>

<summary>Hint 2</summary>

If q was in the sub-tree of node p (case 1), get the parent node of p and replace p in its children list with q.

</details>

<details>

<summary>Hint 3</summary>

If p was the root of the tree, make q the root of the tree.

</details>

[< Previous](../water-bottles "Water Bottles")

　　　　　　　　　　　　　　　　

[Next >](../maximum-number-of-non-overlapping-substrings "Maximum Number of Non-Overlapping Substrings")

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

<p>The <code>edges</code> array is given on the form <code>edges[i] = [a_i, b_i]</code>, which means there is an edge between nodes <code>a_i</code> and <code>b_i</code> in the tree.</p>

<p>Return <em>an array of size <code>n</code></em> where <code>ans[i]</code> is the number of nodes in the subtree of the&nbsp;<code>i^th</code>&nbsp;node which have the same label as node <code>i</code>.</p>

<p>A&nbsp;subtree&nbsp;of a tree&nbsp;<code>T</code> is the tree consisting of a node in <code>T</code> and all of its descendant&nbsp;nodes.</p>

<p>&nbsp;</p>

<p><strong>Example 1:</strong></p>

<img alt="" src="https://assets.leetcode.com/uploads/2020/07/01/q3e1.jpg" style="width: 441px; height: 321px;" />

<pre>

<strong>Input:</strong> n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = &quot;abaedcd&quot;

<strong>Output:</strong> [2,1,1,1,1,1,1]

<strong>Explanation:</strong> Node 0 has label &#39;a&#39; and its sub-tree has node 2 with label &#39;a&#39; as well, thus the answer is 2. Notice that any node is part of its sub-tree.

Node 1 has a label &#39;b&#39;. 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).

</pre>

<p><strong>Example 2:</strong></p>

<img alt="" src="https://assets.leetcode.com/uploads/2020/07/01/q3e2.jpg" style="width: 381px; height: 321px;" />

<pre>

<strong>Input:</strong> n = 4, edges = [[0,1],[1,2],[0,3]], labels = &quot;bbbb&quot;

<strong>Output:</strong> [4,2,1,1]

<strong>Explanation:</strong> 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 &#39;b&#39;, thus the answer is 2.

The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label &#39;b&#39;, thus the answer is 4.

</pre>

<p><strong>Example 3:</strong></p>

<img alt="" src="https://assets.leetcode.com/uploads/2020/07/01/q3e3.jpg" style="width: 381px; height: 321px;" />

<pre>

<strong>Input:</strong> n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = &quot;aabab&quot;

<strong>Output:</strong> [3,2,1,1,1]

</pre>

<p><strong>Example 4:</strong></p>

<pre>

<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = &quot;cbabaa&quot;

<strong>Output:</strong> [1,2,1,1,2,1]

</pre>

<p><strong>Example 5:</strong></p>

<pre>

<strong>Input:</strong> n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = &quot;aaabaaa&quot;

<strong>Output:</strong> [6,5,4,1,3,2,1]

</pre>

<p>&nbsp;</p>

<p><strong>Constraints:</strong></p>

<ul>

<li><code>1 &lt;= n &lt;= 10^5</code></li>

<li><code>edges.length == n - 1</code></li>

<li><code>edges[i].length == 2</code></li>

<li><code>0 &lt;= a_i,&nbsp;b_i &lt; n</code></li>

<li><code>a_i !=&nbsp;b_i</code></li>

<li><code>labels.length == n</code></li>

<li><code>labels</code> is consisting of only of lower-case English letters.</li>

</ul>

[[Depth-first Search](../../tag/depth-first-search/README.md)]

[[Breadth-first Search](../../tag/breadth-first-search/README.md)]

<details>

<summary>Hint 1</summary>

Start traversing the tree and each node should return a vector to its parent node.

</details>

<details>

<summary>Hint 2</summary>

The vector should be of length 26 and have the count of all the labels in the sub-tree of this node.

</details>

<p>&nbsp;</p>

<p><strong>Constraints:</strong></p>

<ul>

<li><code>1 &lt;= n &lt;= 19</code></li>

</ul>