3999. Minimum Number of String Groups Through Transformations

You are given an array of strings words.

Define a transformation on a string s as follows:

• Let E be the subsequence of characters at even indices of s.
• Let O be the subsequence of characters at odd indices of s.
• Independently cyclically shift E and O by any number of positions to the right, possibly zero.
• Reconstruct the string by placing the shifted E characters back into even indices and the shifted O characters back into odd indices.

Two strings are equivalent if one can be transformed into the other by a single transformation.

Partition words into the minimum number of groups such that:

• Every string belongs to exactly one group.
• Every pair of strings in the same group are equivalent.

Return an integer denoting the minimum number of groups.

3997. Count Dominant Nodes in a Binary Tree

You are given the root of a complete binary tree.

A node x is called dominant if its value is equal to the maximum value among all nodes in the subtree rooted at x.

Return the number of dominant nodes in the tree.

4002. Count Valid Sequences

You are given two positive integers n and k.

A valid sequence is a sequence of k positive integers such that:

• The sum of all integers in the sequence is equal to n.
• The product of all integers in the sequence is even.

Return the number of valid sequences. Since the answer may be very large, return it modulo 10^9 + 7.

Two sequences are considered different if they differ at any index. For example, [1, 1, 2] and [1, 2, 1] are considered different sequences.

3996. Even Number of Knight Moves

You are given two integer arrays start and target, where each array is of the form [x, y] representing a cell on a standard 8 x 8 chessboard.

Return true if a knight can move from start to target in an even number of moves. Otherwise, return false.

Note: A valid knight move consists of moving two squares in one direction and one square perpendicular to it. The figure below illustrates all eight possible moves from a cell.

4000. Largest Integer With Given Digit Sum

You are given two non-negative integers n and s.

Return the largest integer that has at most n digits and whose sum of digits is s. If no such integer exists, return -1.

4003. Minimum Cost Path with Alternating Directions III

You are given two integers m and n representing the number of rows and columns of a grid. Your goal is to reach cell (m - 1, n - 1). You are also given a 2D integer array penalty.

The cost to enter cell (i, j) is (i + 1) * (j + 1).

You begin at cell (0, 0) and initially pay its entrance cost. Actions performed after entering (0, 0) are numbered starting from 1.

On each action, you may move to an adjacent cell or wait in the current cell. A move follows the parity rule if:

• On an odd-numbered action, you move right or down.
• On an even-numbered action, you move left or up.

The cost of an action is determined as follows:

• If you move according to the parity rule, pay only the entrance cost of the destination cell.
• If you move in a direction that violates the parity rule, pay the entrance cost of the destination cell plus penalty[i][j], where (i, j) is the cell you move from.
• If you wait in cell (i, j), pay penalty[i][j].

After every move or wait, the action number increases by 1. Therefore, the required parity alternates after every action, regardless of whether a penalty was paid.

Return the minimum total cost required to reach (m - 1, n - 1).

3998. Transform Binary String Using Subsequence Sort

You are given a binary string s.

You are also given an array of strings strs, where each strs[i] has the same length as s and consists of characters '0', '1', and '?'. Each '?' can be replaced by either '0' or '1'.

You may perform the following operation any number of times (including zero):

• Choose any subsequence sub of s.
• Sort sub in non-decreasing order.
• Replace the chosen subsequence in s with the sorted sub, keeping all other characters unchanged.

Return a boolean array ans, where ans[i] is true if it’s possible to replace all '?' in strs[i] with '0' or '1' and transform s into the resulting string using the allowed operation above, otherwise return false.

4006. Count Valid Prefixes

You are given a binary string s.

A prefix of s is considered valid if its characters can be rearranged to form an alternating string.

Return the number of valid prefixes of s.

A string is considered alternating if no two adjacent characters are equal.

4008. Minimum Initial Strength to Defeat All Monsters

You are given an integer array monsters, where monsters[i] represents the strength of the i^th monster.

You are also given a 2D integer array boosts, where boosts[i] = [l_i, r_i, v_i] indicates that v_i is added to your temporary bonus while fighting any monster whose index lies in [l_i, r_i]. Boost ranges may overlap, and the values of all applicable boosts are added together.

You start with a non-negative initial strength and fight the monsters from left to right.

For each monster at index i:

• Let bonus be the sum of the values of all boosts that apply to monster i.
• You can defeat the monster only if your current strength plus bonus is at least monsters[i].
• After defeating the monster, only your current strength decreases by monsters[i]. If it becomes negative, it is set to 0.

Return the minimum initial strength required to defeat all monsters.

Note: The temporary bonus is used only to determine whether the current monster can be defeated. It does not otherwise change your current strength.

4004. Minimum Moves to Balance Circular Array II

You are given a circular array balance of length n, where balance[i] is the net balance of person i.

In one move, a person can transfer exactly 1 unit of balance to either their left or right neighbor.

Return the minimum number of moves required so that every person has a non-negative balance. If it is impossible, return -1.