Solve message splitting and board crushing

Question

LeetCode 2468. Split Message Based on Limit – Given a message string and a per-line width, split it into parts adding the suffix "<i/n>" (e.g., 1/8, 2/ 8). Follow-up: perform the split when the suffix length itself must be counted within the width. LeetCode 723. Candy Crush – Given an m × n board, repeatedly crush all rows or columns containing ≥3 identical adjacent candies, apply gravity, and return the board when it reaches a stable state.

https://leetcode.com/problems/split-message-based-on-limit/description/ https://leetcode.com/problems/candy-crush/description/

Split Message Based on Limit

You are given a string message and a positive integer limit.

You must split message into one or more parts based on limit. Each resulting part should have the suffix "<a/b>", where b is the total number of parts and a is the index of the part (1-indexed, going from 1 to b). The suffix length counts toward limit: the length of each resulting part (including its suffix) must be at most limit, and every part except possibly the last one must be exactly limit characters long. Also, the parts must be split such that the concatenation of all parts (with their suffixes removed) equals message, and you must minimize the number of parts b.

Return the parts as an array of strings. If it is impossible to split message as required, return an empty array.

Example: message = "this is really a very awesome message", limit = 9 -> 14 parts, e.g. "thi<1/14>", "s i<2/14>", ..., "ge<14/14>".

Constraints

• 1 <= message.length <= 10^4
• message consists of only lowercase English letters and spaces (per LeetCode)
• 1 <= limit <= 10^4

Hints

1. The suffix "<a/b>" costs 3 fixed characters plus the digit-lengths of a and b. Once you fix the total number of parts b, the suffix cost per part is fully determined.
2. Iterate over the candidate number of parts b from small to large. For each b, compute the total content capacity = sum over i of (limit - 3 - len(str(i)) - len(str(b))). The first b whose capacity >= len(message) AND that exactly consumes the message is the answer.
3. Any part with non-positive available content space makes that b infeasible — skip it.
4. Because you try b in increasing order, the first feasible b is automatically the minimum.

Candy Crush

This question is about implementing a basic elimination algorithm for Candy Crush.

Given an m x n integer array board representing the grid of candy where board[i][j] represents the type of candy. A value of board[i][j] == 0 represents an empty cell.

The given board represents the state of the game following the player's move. Now, you need to restore the board to a stable state by crushing candies according to the following rules:

1. If three or more candies of the same type are adjacent vertically or horizontally, crush them all at the same time — these positions become empty.
2. After crushing all candies simultaneously, if an empty space on the board has candies on top of itself, then these candies will drop until they hit a candy or the bottom at the same time (no new candies will drop outside the top boundary).
3. After these steps, there may exist more candies that can be crushed. If so, repeat the above steps.
4. If there does not exist more candies that can be crushed (i.e., the board is stable), then return the current board.

Return the stable board.

Constraints

• m == board.length
• n == board[i].length
• 3 <= m, n <= 50
• 1 <= board[i][j] <= 2000 or board[i][j] == 0

Examples

Example 1

Input: ([[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]],)
Output: [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [110, 0, 0, 0, 114], [210, 0, 0, 0, 214], [310, 0, 0, 113, 314], [410, 0, 0, 213, 414], [610, 211, 112, 313, 614], [710, 311, 412, 613, 714], [810, 411, 512, 713, 1014]]

Explanation: The canonical LeetCode 723 example. A column of 1s and other vertical/horizontal triples crush, gravity drops the survivors, and after cascades the board stabilizes with three fully-empty top rows.

Example 2

Input: ([[1,3,5,5,2],[3,4,3,3,1],[3,2,4,5,2],[2,4,4,5,5],[1,4,4,1,1]],)
Output: [[1, 3, 0, 0, 0], [3, 4, 0, 5, 2], [3, 2, 0, 3, 1], [2, 4, 0, 5, 2], [1, 4, 3, 1, 1]]

Explanation: Vertical run of 4s in column 2 crushes; after gravity the rest of the board is stable with that column partly emptied at the top.

Hints

1. Scan separately for horizontal and vertical runs of 3+ identical candies. Use a marking pass so all crushes are detected from the SAME board state before any cell is zeroed (simultaneous crushing).
2. A clean way to mark: collect all (row, col) coordinates that belong to any run of length >= 3 into a set, then zero them all at once.
3. After zeroing, apply gravity column by column: write surviving (non-zero) values from the bottom up, then fill the remaining top cells with 0.
4. Repeat the whole detect-crush-gravity cycle until a full pass finds nothing to crush — that signals the board is stable.