DEV Community: MD ARIFUL HAQUE

3653. XOR After Range Multiplication Queries I

MD ARIFUL HAQUE — Wed, 08 Apr 2026 05:40:45 +0000

3653. XOR After Range Multiplication Queries I

Difficulty: Medium

Topics: Senior, Array, Divide and Conquer, Simulation, Weekly Contest 463

You are given an integer array nums of length n and a 2D integer array queries of size q, where queries[i] = [lᵢ, rᵢ, kᵢ, vᵢ].

For each query, you must apply the following operations in order:

Set idx = lᵢ.
While idx <= rᵢ:
- Update: nums[idx] = (nums[idx] * vᵢ) % (10⁹ + 7)
- Set idx += kᵢ.

Return the bitwise XOR of all elements in nums after processing all queries.

Example 1:

Input: nums = [1,1,1], queries = [[0,2,1,4]]
Output: 4
Explanation:
- A single query [0, 2, 1, 4] multiplies every element from index 0 through index 2 by 4.
- The array changes from [1, 1, 1] to [4, 4, 4].
- The XOR of all elements is 4 ^ 4 ^ 4 = 4.

Example 2:

Input: nums = [2,3,1,5,4], queries = [[1,4,2,3],[0,2,1,2]]
Output: 31
Explanation:
- The first query [1, 4, 2, 3] multiplies the elements at indices 1 and 3 by 3, transforming the array to [2, 9, 1, 15, 4].
- The second query [0, 2, 1, 2] multiplies the elements at indices 0, 1, and 2 by 2, resulting in [4, 18, 2, 15, 4].
- Finally, the XOR of all elements is 4 ^ 18 ^ 2 ^ 15 ^ 4 = 31.

Constraints:

1 <= n == nums.length <= 10³
1 <= nums[i] <= 10⁹
1 <= q == queries.length <= 10³
queries[i] = [lᵢ, rᵢ, kᵢ, vᵢ]
0 <= lᵢ <= rᵢ < n
1 <= kᵢ <= n
1 <= vᵢ <= 10⁵

Hint:

Use bruteforce

Solution:

The problem requires applying several range multiplication updates to an array, where each update multiplies indices lᵢ, lᵢ + kᵢ, lᵢ + 2kᵢ, ... ≤ rᵢ by vᵢ modulo 10⁹ + 7. After processing all queries, return the XOR of all array elements. The brute-force approach is feasible due to constraints (n, q ≤ 1000).

Approach:

Use direct simulation for each query: iterate over the specified indices and multiply each element by vᵢ modulo 10⁹ + 7.
After all queries, compute the XOR of all elements.
No need for advanced data structures because n and q are small.

Let's implement this solution in PHP: 3653. XOR After Range Multiplication Queries I

<?php
/**
 * @param Integer[] $nums
 * @param Integer[][] $queries
 * @return Integer
 */
function xorAfterQueries(array $nums, array $queries): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$nums1 = [1, 1, 1];
$queries1 = [[0, 2, 1, 4]];
echo xorAfterQueries($nums1, $queries1) . "\n"; // Output: 4

$nums2 = [2, 3, 1, 5, 4];
$queries2 = [[1, 4, 2, 3], [0, 2, 1, 2]];
echo xorAfterQueries($nums2, $queries2) . "\n"; // Output: 31
?>

Explanation:

Step 1: Loop through each query [l, r, k, v].
Step 2: For each query, start from index l and step by k until r, multiplying nums[idx] by v modulo 10⁹ + 7.
Step 3: After processing all queries, XOR all elements together.
Step 4: Return the XOR result.

Complexity

Time Complexity: O(q⋅(n/k))≤O(q⋅n) in worst case (when k=1), so O(10⁶) operations maximum, fine for given constraints.
Space Complexity: O(1) extra space (excluding input storage).

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

2069. Walking Robot Simulation II

MD ARIFUL HAQUE — Tue, 07 Apr 2026 10:11:11 +0000

2069. Walking Robot Simulation II

Difficulty: Medium

Topics: Senior, Design, Simulation, Biweekly Contest 65

A width x height grid is on an XY-plane with the bottom-left cell at (0, 0) and the top-right cell at (width - 1, height - 1). The grid is aligned with the four cardinal directions ("North", "East", "South", and "West"). A robot is initially at cell (0, 0) facing direction "East".

The robot can be instructed to move for a specific number of steps. For each step, it does the following.

Attempts to move forward one cell in the direction it is facing.
If the cell the robot is moving to is out of bounds, the robot instead turns 90 degrees counterclockwise and retries the step.

After the robot finishes moving the number of steps required, it stops and awaits the next instruction.

Implement the Robot class:

Robot(int width, int height) Initializes the width x height grid with the robot at (0, 0) facing "East".
void step(int num) Instructs the robot to move forward num steps.
int[] getPos() Returns the current cell the robot is at, as an array of length 2, [x, y].
String getDir() Returns the current direction of the robot, "North", "East", "South", or "West".

Example 1:

Input:

      ["Robot", "step", "step", "getPos", "getDir", "step", "step", "step", "getPos", "getDir"]
      [[6, 3], [2], [2], [], [], [2], [1], [4], [], []]

Output: [null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]
Explanation:

     Robot robot = new Robot(6, 3); // Initialize the grid and the robot at (0, 0) facing East.
     robot.step(2);  // It moves two steps East to (2, 0), and faces East.
     robot.step(2);  // It moves two steps East to (4, 0), and faces East.
     robot.getPos(); // return [4, 0]
     robot.getDir(); // return "East"
     robot.step(2);  // It moves one step East to (5, 0), and faces East.
     // Moving the next step East would be out of bounds, so it turns and faces North.
     // Then, it moves one step North to (5, 1), and faces North.
     robot.step(1);  // It moves one step North to (5, 2), and faces North (not West).
     robot.step(4);  // Moving the next step North would be out of bounds, so it turns and faces West.
     // Then, it moves four steps West to (1, 2), and faces West.
     robot.getPos(); // return [1, 2]
     robot.getDir(); // return "West"

Constraints:

2 <= width, height <= 100
1 <= num <= 10⁵
At most 10⁴ calls in total will be made to step, getPos, and getDir.

Hint:

The robot only moves along the perimeter of the grid. Can you think if modulus can help you quickly compute which cell it stops at?
After the robot moves one time, whenever the robot stops at some cell, it will always face a specific direction. i.e., The direction it faces is determined by the cell it stops at.
Can you precompute what direction it faces when it stops at each cell along the perimeter, and reuse the results?

Solution:

The robot moves only along the perimeter of the grid.

The key insight is that after the first move, the robot’s behavior becomes periodic — it repeats the same cycle of positions and directions along the perimeter every 2*(width + height - 2) steps.

We can use modulo arithmetic to reduce large step counts, but must handle the starting position (0,0) with direction "East" carefully to ensure correct final direction.

Approach:

Recognize that the robot never enters the interior — it always moves along the outer boundary.
The number of cells on the perimeter (excluding duplicates) is 2*(width + height - 2).
Use modulo to reduce num steps to a smaller number without changing the final position or direction, except when the robot would stay at (0,0) facing East.
Simulate the reduced number of steps step-by-step, handling boundary collisions by turning left.
Predefine directions in the order ["East", "North", "West", "South"] to easily rotate.

Let's implement this solution in PHP: 2069. Walking Robot Simulation II

<?php
class Robot {

    private int $width;
    private int $height;
    private int $x;
    private int $y;
    private string $dir;
    private int|float $perimeter;
    private array $directions;

    /**
     * @param Integer $width
     * @param Integer $height
     */
    function __construct(int $width, int $height) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param Integer $num
     * @return NULL
     */
    function step(int $num) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @return Integer[]
     */
    function getPos(): array
    {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @return String
     */
    function getDir(): string
    {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @return void
     */
    private function turnLeft(): void
    {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

/**
 * Your Robot object will be instantiated and called as such:
 * $obj = Robot($width, $height);
 * $obj->step($num);
 * $ret_2 = $obj->getPos();
 * $ret_3 = $obj->getDir();
 */

// Test cases
$robot = new Robot(6, 3);
$robot->step(2);   // (2,0), East
$robot->step(2);   // (4,0), East
$robot->getPos();  // [4,0]
$robot->getDir();  // "East"
$robot->step(2);   // (5,1), North
$robot->step(1);   // (5,2), North
$robot->step(4);   // (1,2), West
$robot->getPos();  // [1,2]
$robot->getDir();  // "West"

/**Edge case: Full cycle**/
$robot = new Robot(3, 3);
$robot->step(8);   // Full perimeter (8 steps) → should be back at (0,0) facing East
$robot->getPos();  // [0,0]
$robot->getDir();  // "East"

/**Edge case: Small grid 2x2**/
$robot = new Robot(2, 2);
$robot->step(4);   // Full cycle, back to start facing East
$robot->getPos();  // [0,0]
$robot->getDir();  // "East"
?>

Explanation:

Periodic movement: The robot’s path along the perimeter repeats every 2*(width + height - 2) steps.
Step reduction:
- num = num % perimeter avoids large loops.
- If the result is 0 and the robot is at (0,0) facing East, we must simulate a full cycle to get the correct final direction.
Simulation loop:
- For each step, try to move forward.
- If the next cell is out of bounds, turn left and retry the same step (without moving).
Direction tracking:
- Keep the current direction index in $directions array.
- Turning left means incrementing the index modulo 4.
Special case:
- If width == 2 and height == 2, the perimeter is 4 cells, and the starting point is a corner.
- The modulo logic still works because the robot will never stay in starting position unless num % perimeter == 0, which is handled by simulating the full cycle.

Complexity

Time Complexity: per step call:
- After modulo reduction, at most O(perimeter) steps, but perimeter <= 2*(100+100-2) = 396, so it’s effectively constant time per call.
- Actually, with modulo, we reduce to at most perimeter steps, which is small (≤ 400).
- Better: We can compute directly without per-step loop using mathematical positions, but here we still loop.
Space Complexity: O(1) extra space beyond input.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

657. Robot Return to Origin

MD ARIFUL HAQUE — Sun, 05 Apr 2026 00:58:47 +0000

657. Robot Return to Origin

Difficulty: Easy

Topics: Mid Level, String, Simulation

There is a robot starting at the position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.

You are given a string moves that represents the move sequence of the robot where moves[i] represents its iᵗʰ move. Valid moves are 'R' (right), 'L' (left), 'U' (up), and 'D' (down).

Return true if the robot returns to the origin after it finishes all of its moves, or false otherwise.

Note: The way that the robot is "facing" is irrelevant. 'R' will always make the robot move to the right once, 'L' will always make it move left, etc. Also, assume that the magnitude of the robot's movement is the same for each move.

Example 1:

Input: moves = "UD"
Output: true
Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.

Example 2:

Input: moves = "LL"
Output: false
Explanation: The robot moves left twice. It ends up two "moves" to the left of the origin. We return false because it is not at the origin at the end of its moves.

Example 3:

Input: moves = "RRDD"
Output: false

Example 4:

Input: moves = "LDRL"
Output: false

Example 5:

Input: moves = "RLUDRLD"
Output: true

Example 6:

Input: moves = ""
Output: true

Constraints:

1 <= moves.length <= 2 * 10⁴
moves only contains the characters 'U', 'D', 'L' and 'R'.

Solution:

The robot starts at the origin (0, 0). After a series of moves (U, D, L, R), it returns to the origin if and only if the number of up moves equals the number of down moves and the number of left moves equals the number of right moves. The solution counts each move type and compares the counts.

Approach:

Count the frequency of each move character in the string.
Compare the count of 'U' with 'D' — they must be equal to cancel vertical movement.
Compare the count of 'L' with 'R' — they must be equal to cancel horizontal movement.
Return true if both conditions hold, otherwise false.

Let's implement this solution in PHP: 657. Robot Return to Origin

<?php
/**
 * @param String $moves
 * @return Boolean
 */
function judgeCircle(string $moves): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo judgeCircle("UD") . "\n";              // Output: true
echo judgeCircle("LL") . "\n";              // Output: false
echo judgeCircle("RRDD") . "\n";            // Output: false
echo judgeCircle("LDRL") . "\n";            // Output: false
echo judgeCircle("RLUDRLD") . "\n";         // Output: true
echo judgeCircle("") . "\n";                // Output: true
?>

Explanation:

The robot’s position changes by (x, y) where:
- 'U' increments y
- 'D' decrements y
- 'R' increments x
- 'L' decrements x
To end at (0, 0), total change in x must be 0 and total change in y must be 0.
This is equivalent to: count('U') == count('D') and count('L') == count('R').
The solution uses array_count_values to get counts, then checks these equalities with null coalescing to handle missing moves.

Complexity

Time Complexity: O(n), str_split and array_count_values each traverse the string once.
Space Complexity: O(1), Only stores counts for 4 possible characters.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

2075. Decode the Slanted Ciphertext

MD ARIFUL HAQUE — Sat, 04 Apr 2026 09:56:13 +0000

2075. Decode the Slanted Ciphertext

Difficulty: Medium

Topics: Staff, String, Simulation, Weekly Contest 267

A string originalText is encoded using a slanted transposition cipher to a string encodedText with the help of a matrix having a fixed number of rows rows.

originalText is placed first in a top-left to bottom-right manner.

The blue cells are filled first, followed by the red cells, then the yellow cells, and so on, until we reach the end of originalText. The arrow indicates the order in which the cells are filled. All empty cells are filled with ' '. The number of columns is chosen such that the rightmost column will not be empty after filling in originalText.

encodedText is then formed by appending all characters of the matrix in a row-wise fashion.

The characters in the blue cells are appended first to encodedText, then the red cells, and so on, and finally the yellow cells. The arrow indicates the order in which the cells are accessed.

For example, if originalText = "cipher" and rows = 3, then we encode it in the following manner:

The blue arrows depict how originalText is placed in the matrix, and the red arrows denote the order in which encodedText is formed. In the above example, encodedText = "ch ie pr".

Given the encoded string encodedText and number of rows rows, return the original string originalText.

Note: originalText does not have any trailing spaces ' '. The test cases are generated such that there is only one possible originalText.

Example 1:

Input: encodedText = "ch ie pr", rows = 3
Output: "cipher"
Explanation: This is the same example described in the problem description.

Example 2:

Input: encodedText = "iveo eed l te olc", rows = 4
Output: "i love leetcode"
Explanation: The figure above denotes the matrix that was used to encode originalText. The blue arrows show how we can find originalText from encodedText.

Example 3:

Input: encodedText = "coding", rows = 1
Output: "coding"
Explanation: Since there is only 1 row, both originalText and encodedText are the same.

Example 4:

Input: encodedText = "abc ", rows = 2
Output: "abc"

Example 5:

Input: encodedText = "a ", rows = 2
Output: "a"

Constraints:

0 <= encodedText.length <= 10⁶
encodedText consists of lowercase English letters and ' ' only.
encodedText is a valid encoding of some originalText that does not have trailing spaces.
1 <= rows <= 1000
The testcases are generated such that there is only one possible originalText.

Hint:

How can you use rows and encodedText to find the number of columns of the matrix?
Once you have the number of rows and columns, you can create the matrix and place encodedText in it. How should you place it in the matrix?
How should you traverse the matrix to "decode" originalText?

Solution:

The solution decodes a slanted transposition cipher by reconstructing the original matrix from the encoded string, then reading it in a diagonal order from the first row to the last column. The number of columns is derived from the encoded text length and the given number of rows. The result is trimmed of trailing spaces as per the problem constraints.

Approach:

Calculate number of columns: Since the encoded text is formed by reading the matrix row-wise, columns = len(encodedText)/rows. (The problem guarantees the rightmost column is not empty, so division is exact.)
Simulate diagonal traversal
- The original text was placed in the matrix in a top-left to bottom-right (diagonal) order.
- Therefore, to decode, we traverse all diagonals starting from the first row, each beginning at (0, startCol) for startCol = 0 to columns - 1.
Extract characters in diagonal order
- For each diagonal, move (row+1, col+1) until we exceed matrix bounds.
- Convert 2D coordinates to 1D index: row * columns + col, and append the character from encodedText to the result.
Remove trailing spaces: The problem states originalText has no trailing spaces, so we trim the result.

Let's implement this solution in PHP: 2075. Decode the Slanted Ciphertext

<?php
/**
 * @param String $encodedText
 * @param Integer $rows
 * @return String
 */
function decodeCiphertext(string $encodedText, int $rows): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo decodeCiphertext("ch   ie   pr", 3) . "\n";                        // Output: "cipher"
echo decodeCiphertext("iveo    eed   l te   olc", 4) . "\n";            // Output: "i love leetcode"
echo decodeCiphertext("coding", 1) . "\n";                              // Output: "coding"
echo decodeCiphertext("abc ", 2) . "\n";                                // Output: "abc"
echo decodeCiphertext("a ", 2) . "\n";                                  // Output: "a"
?>

Explanation:

Step 1 – Find matrix dimensions: We know rows. The number of columns is simply len(encodedText) / rows because the encoded string is a concatenation of all rows of the matrix, and the matrix is fully filled (no empty cells except those intentionally filled with spaces for alignment).
Step 2 – Understand encoding order: Original text was written diagonally: first (0,0), then (1,1), (2,2), … until the end of the matrix. After finishing one diagonal, we move to the next starting column in row 0.
Step 3 – Reverse the process: To decode, we collect characters in the same diagonal order as they were written. That’s why we iterate over startCol from 0 to columns-1 and for each, move down-right until we hit the bottom or right edge.
Step 4 – Handle spaces: Spaces in the encoded text represent empty cells in the matrix. They are correctly included during diagonal traversal and removed at the end.

Complexity

Time Complexity: O(n), Where n is the length of encodedText. Each character is visited exactly once during the diagonal traversal.
Space Complexity: O(1) extra space (excluding output). The algorithm works in-place on the input string and builds the result incrementally.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3661. Maximum Walls Destroyed by Robots

MD ARIFUL HAQUE — Fri, 03 Apr 2026 10:25:13 +0000

3661. Maximum Walls Destroyed by Robots

Difficulty: Hard

Topics: Senior Staff, Array, Binary Search, Dynamic Programming, Sorting, Weekly Contest 464

There is an endless straight line populated with some robots and walls. You are given integer arrays robots, distance, and walls:

robots[i] is the position of the iᵗʰ robot.
distance[i] is the maximum distance the iᵗʰ robot's bullet can travel.
walls[j] is the position of the jᵗʰ wall.

Every robot has one bullet that can either fire to the left or the right at most distance[i] meters.

A bullet destroys every wall in its path that lies within its range. Robots are fixed obstacles: if a bullet hits another robot before reaching a wall, it immediately stops at that robot and cannot continue.

Return the maximum number of unique walls that can be destroyed by the robots.

Notes:

A wall and a robot may share the same position; the wall can be destroyed by the robot at that position.
Robots are not destroyed by bullets.

Example 1:

Input: robots = [4], distance = [3], walls = [1,10]
Output: 1
Explanation:
- robots[0] = 4 fires left with distance[0] = 3, covering [1, 4] and destroys walls[0] = 1.
- Thus, the answer is 1.

Example 2:

Input: robots = [10,2], distance = [5,1], walls = [5,2,7]
Output: 3
Explanation:
- robots[0] = 10 fires left with distance[0] = 5, covering [5, 10] and destroys walls[0] = 5 and walls[2] = 7.
- robots[1] = 2 fires left with distance[1] = 1, covering [1, 2] and destroys walls[1] = 2.
- Thus, the answer is 3.

Example 3:

Input: robots = [1,2], distance = [100,1], walls = [10]
Output: 0
Explanation: In this example, only robots[0] can reach the wall, but its shot to the right is blocked by robots[1]; thus the answer is 0.

Example 4:

Input: robots = [17,59,32,11,72,18], distance = [5,7,6,5,2,10], walls = [17,25,33,29,54,53,18,35,39,37,20,14,34,13,16,58,22,51,56,27,10,15,12,23,45,43,21,2,42,7,32,40,8,9,1,5,55,30,38,4,3,31,36,41,57,28,11,49,26,19,50,52,6,47,46,44,24,48]
Output: 37

Constraints:

1 <= robots.length == distance.length <= 10⁵
1 <= walls.length <= 10⁵
1 <= robots[i], walls[j] <= 10⁹
1 <= distance[i] <= 10⁵
All values in robots are unique
All values in walls are unique

Hint:

Sort both the robots and walls arrays. This will help in efficiently processing positions and performing range queries.
Each robot can shoot either left or right. However, if a robot fires and another robot is in its path, the bullet stops. You need to use the positions of neighboring robots to limit the shooting range.
Use binary search (lower_bound and upper_bound) to count how many walls fall within a certain range.
You can use dynamic programming to keep track of the maximum number of walls destroyed so far, depending on the direction the previous robot shot.

Solution:

The problem requires maximizing the number of unique walls destroyed by robots, each with a single bullet that travels left or right up to a given distance. Bullets stop if they hit another robot.

The solution uses sorting, binary search for efficient range queries, and dynamic programming (DP) with memoization to handle the state of whether a robot shoots left or right, while respecting blockage constraints from adjacent robots.

Approach:

Sorting: Both robots and walls are sorted by position to allow binary search and linear DP processing.
DP State Definition: dp[i][direction] = maximum walls destroyed considering robots from 0..i, where direction indicates whether robot i shoots left (0) or right (1).
Range Limiting Due to Adjacent Robots
- When a robot shoots left, the left bound is capped by the next robot to its left (if any) plus one, to avoid being blocked.
- When shooting right, the right bound is capped by the next robot to its right, depending on its planned direction.
Wall Counting via Binary Search: For a given interval [leftBound, rightBound], the number of walls destroyed is found using lowerBound on the sorted walls array.
Memoized Recursion: Start from the last robot and work backwards, trying both shooting directions and taking the maximum over all possibilities.

Let's implement this solution in PHP: 3661. Maximum Walls Destroyed by Robots

<?php
/**
 * @param integer[] $robots
 * @param integer[] $distance
 * @param integer[] $walls
 * @return integer
 */
function maxWalls(array $robots, array $distance, array $walls): int {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Binary search: find first index where value >= target
 * @param integer[] $arr
 * @param integer $target
 * @return integer
 */
function lowerBound(array $arr, int $target): int {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maxWallsDestroyed([4], [3], [1,10]) . "\n";                // Output: 1
echo maxWallsDestroyed([10,2], [5,1], [5,2,7]) . "\n";          // Output: 3
echo maxWallsDestroyed([1,2], [100,1], [10]) . "\n";            // Output: 0
echo maxWallsDestroyed([17,59,32,11,72,18], [5,7,6,5,2,10], [17,25,33,29,54,53,18,35,39,37,20,14,34,13,16,58,22,51,56,27,10,15,12,23,45,43,21,2,42,7,32,40,8,9,1,5,55,30,38,4,3,31,36,41,57,28,11,49,26,19,50,52,6,47,46,44,24,48]) . "\n";            // Output: 37
?>

Explanation:

Step 1: Preprocessing: Pair each robot with its distance, then sort robots by position. Sort walls array for binary search.
Step 2: DP Base Case: If no robots remain, return 0 walls destroyed.
Step 3: Left Shot Calculation
- Leftmost reach = robotPos - distance.
- If there’s a robot to the left, limit left reach to leftRobotPos + 1.
- Count walls in [leftBound, robotPos] via binary search.
Step 4: Right Shot Calculation
- Rightmost reach = robotPos + distance.
- If there’s a robot to the right, limit right reach based on whether that robot will shoot left (then use its left bound) or right (then avoid its position).
- Count walls in [robotPos, rightBound] via binary search.
Step 5: Memoization: Store results in dp to avoid recomputation.
Step 6: Final Answer: Start recursion from the last robot with direction = 1 (right), since the last robot has no right neighbor to block.

Complexity

Time Complexity:
- Sorting robots and walls: O(n log n + m log m) where n = robots length, m = walls length.
- Each DP state (n, 2) computed once, each using O(log m) for binary search.
- Total: O(n log m + n log n + m log m) ≈ O(n log n + m log m).
Space Complexity:
- O(n + m) for DP table and sorted arrays.
- Recursion stack depth up to O(n).

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3418. Maximum Amount of Money Robot Can Earn

MD ARIFUL HAQUE — Thu, 02 Apr 2026 05:45:50 +0000

3418. Maximum Amount of Money Robot Can Earn

Difficulty: Medium

Topics: Staff, Array, Dynamic Programming, Matrix, Weekly Contest 432

You are given an m x n grid. A robot starts at the top-left corner of the grid (0, 0) and wants to reach the bottom-right corner (m - 1, n - 1). The robot can move either right or down at any point in time.

The grid contains a value coins[i][j] in each cell:

If coins[i][j] >= 0, the robot gains that many coins.
If coins[i][j] < 0, the robot encounters a robber, and the robber steals the absolute value ofcoins[i][j] coins.

The robot has a special ability to neutralize robbers in at most 2 cells on its path, preventing them from stealing coins in those cells.

Note: The robot's total coins can be negative.

Return the maximum profit the robot can gain on the route.

Example 1:

Input: coins = [[0,1,-1],[1,-2,3],[2,-3,4]]
Output: 8
Explanation: An optimal path for maximum coins is:
1. Start at (0, 0) with 0 coins (total coins = 0).
2. Move to (0, 1), gaining 1 coin (total coins = 0 + 1 = 1).
3. Move to (1, 1), where there's a robber stealing 2 coins. The robot uses one neutralization here, avoiding the robbery (total coins = 1).
4. Move to (1, 2), gaining 3 coins (total coins = 1 + 3 = 4).
5. Move to (2, 2), gaining 4 coins (total coins = 4 + 4 = 8).

Example 2:

Input: coins = [[10,10,10],[10,10,10]]
Output: 40
Explanation: An optimal path for maximum coins is:
1. Start at (0, 0) with 10 coins (total coins = 10).
2. Move to (0, 1), gaining 10 coins (total coins = 10 + 10 = 20).
3. Move to (0, 2), gaining another 10 coins (total coins = 20 + 10 = 30).
4. Move to (1, 2), gaining the final 10 coins (total coins = 30 + 10 = 40).

Constraints:

m == coins.length
n == coins[i].length
1 <= m, n <= 500
-1000 <= coins[i][j] <= 1000

Hint:

Use Dynamic Programming.
Let dp[i][j][k] denote the maximum amount of money a robot can earn by starting at cell (i,j) and having neutralized k robbers.

Solution:

The problem asks for the maximum coins a robot can collect while moving from the top‑left to the bottom‑right of an m x n grid, moving only right or down. Each cell contains a coin value (positive = gain, negative = robbery). The robot can neutralise at most 2 robberies (i.e., treat the cell’s value as 0 instead of its negative amount). The solution uses 3D dynamic programming where dp[i][j][k] stores the best total coins reachable at cell (i,j) after using exactly k neutralisations (k = 0,1,2). The answer is the maximum of the three states at the destination. The provided PHP implementation uses space‑optimised 1D arrays for each k and processes the grid row by row.

Approach:

DP state definition: dp[i][j][k] = maximum coins earned when reaching cell (i,j) with exactly k neutralisations already used (k = 0,1,2).
Base case: At (0,0), the robot starts with the cell’s value:
- k = 0: dp[0][0][0] = coins[0][0]
- k = 1: dp[0][0][1] = 0 if coins[0][0] < 0 (neutralise the starting cell), otherwise impossible (-∞).
- k = 2: impossible (-∞).
Transitions: For each cell (i,j), the robot can come from top (i-1,j) or left (i,j-1). For each k:
1. Do not neutralise current cell – add coins[i][j] to the best of the two predecessors that used exactly k neutralisations.
2. Neutralise current cell (only if coins[i][j] < 0 and k ≥ 1) – add 0 instead of the negative value, using exactly k-1 neutralisations from the predecessor.
Implementation optimisation: Because only the previous row and current row are needed, the DP is stored in three 1D arrays (prev0, prev1, prev2 for the previous row, and cur0, cur1, cur2 for the current row). After processing each row, the current arrays become the previous ones for the next row.
Final answer: max(dp[m-1][n-1][0], dp[m-1][n-1][1], dp[m-1][n-1][2])

Let's implement this solution in PHP: 3418. Maximum Amount of Money Robot Can Earn

<?php
/**
 * @param Integer[][] $coins
 * @return Integer
 */
function maximumAmount(array $coins): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maximumAmount([[0,1,-1],[1,-2,3],[2,-3,4]]) . "\n";        // Output: 8
echo maximumAmount([[10,10,10],[10,10,10]]) . "\n";             // Output: 40
?>

Explanation:

Why three states? The robot can neutralise at most 2 robbers. Keeping track of exactly how many neutralisations have been used allows us to correctly decide whether neutralising the current cell is allowed and what the resulting state should be.
Handling negative values: If a cell contains a negative number, the robot can either:
- Accept the loss (add the negative value) – this does not increase the neutralisation count.
- Use one of its remaining neutralisations (if any) – treat the value as 0 and increase the neutralisation count by 1.
Avoiding invalid states: States that are unreachable are initialised to a very small number (-INF). For example, dp[0][0][1] is possible only if the starting cell is negative; otherwise it stays -INF. The same logic applies when moving from a predecessor that itself is unreachable.
Space efficiency: The full 3D table would be O(m * n * 3) memory, which for m,n ≤ 500 is about 750,000 entries – acceptable. However, the provided implementation reduces memory to O(n * 3) by only keeping two rows at a time, which is more efficient and still straightforward.
Correctness: The DP explores every possible path (right/down moves) and every possible way of choosing up to 2 neutralisations. Because the robot cannot go back, the principle of optimality holds – the best way to reach (i,j) with a given number of neutralisations depends only on the best ways to reach its predecessors.

Complexity

Time Complexity: O(m * n * 3) = O(m * n), Each cell processes three states, each requiring a constant number of operations (comparing two incoming directions and possibly a neutralisation option).
Space Complexity: O(n * 3) = O(n), Only three arrays for the previous row and three for the current row are stored, each of length n. This is significantly better than a full 3D table.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3474. Lexicographically Smallest Generated String

MD ARIFUL HAQUE — Tue, 31 Mar 2026 18:00:15 +0000

3474. Lexicographically Smallest Generated String

Difficulty: Hard

Topics: Principal, String, Greedy, String Matching, Weekly Contest 439

You are given two strings, str1 and str2, of lengths n and m, respectively.

A string word of length n + m - 1 is defined to be generated by str1 and str2 if it satisfies the following conditions for each index 0 <= i <= n - 1:

If str1[i] == 'T', the substring¹ of word with size m starting at index i is equal to str2, i.e., word[i..(i + m - 1)] == str2.
If str1[i] == 'F', the substring¹ of word with size m starting at index i is not equal to str2, i.e., word[i..(i + m - 1)] != str2.

Return the lexicographically smallest² possible string that can be generated by str1 and str2. If no string can be generated, return an empty string "".

Example 1:

Input: str1 = "TFTF", str2 = "ab"
Output: "ababa"
Explanation: The table below represents the string "ababa"

Index	T/F	Substring of length `m`
0	`'T'`	"ab"
1	`'F'`	"ba"
2	`'T'`	"ab"
3	`'F'`	"ba"

The strings "ababa" and "ababb" can be generated by str1 and str2.
Return "ababa" since it is the lexicographically smaller string.

Example 2:

Input: str1 = "TFTF", str2 = "abc"
Output: ""
Explanation: No string that satisfies the conditions can be generated.

Example 3:

Input: str1 = "F", str2 = "d"
Output: "a"

Example 4:

Input: str1 = "bababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababaaa", str2 = "bab"
Output: "babbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabaaa"

Example 5:

Input: str1 = "TT", str2 = "ab"
Output: "aba"
Explanation: Overlapping T constraints merge correctly

Example 6:

Input: str1 = "FF", str2 = "aa"
Output: "aba"
Explanation: Both substrings must not equal "aa"

Constraints:

1 <= n == str1.length <= 10⁴
1 <= m == str2.length <= 500
str1 consists only of 'T' or 'F'.
str2 consists only of lowercase English characters.

Hint:

Use dynamic programming.
Fill the fixed part.
Use KMP's next table for DP.
The state is the prefix length and the longest suffix length that matches the pattern.
Each unknown character can be selected from ['a', 'b'].
Can you think of a greedy approach?

Solution:

We must construct a string word of length n + m - 1. Each index i in str1 imposes a rule on the substring word[i..i+m-1]:

'T' → must equal str2
'F' → must not equal str2
- To obtain the lexicographically smallest string, we:
- First enforce all 'T' constraints.
- Fill remaining characters with 'a'.
- Then adjust positions to satisfy 'F' constraints by changing characters to 'b' if needed.
- If at any step a constraint cannot be satisfied, return "".

Approach:

Determine the final word length:
- N = n + m - 1
Create an array word initialized with placeholder characters.
Process 'T' constraints:
- Force substrings to match str2.
Fill remaining unknown characters with 'a'.
Track which characters are modifiable.
Process 'F' constraints:
- If a forbidden substring equals str2, modify the rightmost changeable character.
Convert the character array to a string and return it.

Let's implement this solution in PHP: 3474. Lexicographically Smallest Generated String

<?php
/**
 * @param String $str1
 * @param String $str2
 * @return String
 */
function generateString(string $str1, string $str2): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $word
 * @param $str2
 * @param $i
 * @param $m
 * @return bool
 */
function isSame(&$word, $str2, $i, $m): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo generateString("TFTF", "ab") . "\n";           // Output: "ababa"
echo generateString("TFTF", "abc") . "\n";          // Output: ""
echo generateString("F", "d") . "\n";               // Output: "a"
echo generateString("bababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababaaa", "bab") . "\n";               
// Output: echo generateString("bababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababaaa", "bab") . "\n";               // Output: "babbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabaaa"
echo generateString("TT", "ab") . "\n";               // Output: "aba"
echo generateString("FF", "aa") . "\n";               // Output: "aba"
?>

Explanation:

Determine Final Word Length
- The constructed word must allow every index i in str1 to contain a substring of length m.
- Therefore: N = n + m - 1
- Example:

      n = 4
      m = 2
      N = 5

Initialize Word
- Use placeholder $ for unknown characters.
- Example: word = ['$','$','$','$','$']
Process 'T' Conditions
- For every i where str1[i] == 'T': word[i .. i+m-1] = str2
- If the position already contains a conflicting character → return "".
- Example:
```
  str1 = TFTF
  str2 = ab
```

After applying 'T':

      index 0 -> "ab"
      index 2 -> "ab"

      word = a b a b $

Fill Remaining Characters
- To achieve the lexicographically smallest string, fill unused positions with 'a'. word = a b a b a
- Also track which positions can still change.
Process 'F' Conditions
- For each i where: str1[i] == 'F'
- Check: word[i..i+m-1] == str2
- If equal → we must break the match.
- Strategy:
  - Change the rightmost changeable character inside the substring.
  - Replace 'a' with 'b'.
- Why rightmost?
  - Keeps earlier characters smaller → preserves lexicographic minimality.
Edge Case
- If the substring matches str2 but no character can be modified, then: return "" because the constraint cannot be satisfied.

Complexity

Time Complexity:
- Applying 'T' constraints → O(n * m)
- Checking 'F' constraints → O(n * m)
- Overall: O(n * m)
- Where:
- n ≤ 10⁴
- m ≤ 500
- Worst case ≈ 5 × 10⁶ operations.
Space Complexity:
- Word array: O(n + m)
- Changeable flags: O(n + m)
- Total: O(n + m)

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

Substring: A substring is a contiguous non-empty sequence of characters within a string. ↩
Lexicographically Smaller: A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the shorter string is the lexicographically smaller one. ↩

2840. Check if Strings Can be Made Equal With Operations II

MD ARIFUL HAQUE — Mon, 30 Mar 2026 15:29:35 +0000

2840. Check if Strings Can be Made Equal With Operations II

Difficulty: Medium

Topics: Senior, Hash Table, String, Sorting, Biweekly Contest 112

You are given two strings s1 and s2, both of length n, consisting of lowercase English letters.

You can apply the following operation on any of the two strings any number of times:

Choose any two indices i and j such that i < j and the difference j - i is even, then swap the two characters at those indices in the string.

Return true if you can make the strings s1 and s2 equal, and false otherwise.

Example 1:

Input: s1 = "abcdba", s2 = "cabdab"
Output: true
Explanation: We can apply the following operations on s1:
- Choose the indices i = 0, j = 2. The resulting string is s1 = "cbadba".
- Choose the indices i = 2, j = 4. The resulting string is s1 = "cbbdaa".
- Choose the indices i = 1, j = 5. The resulting string is s1 = "cabdab" = s2.

Example 2:

Input: s1 = "abe", s2 = "bea"
Output: false
Explanation: It is not possible to make the two strings equal.

Example 3:

Input: s1 = "abc", s2 = "cba"
Output: true

Constraints:

n == s1.length == s2.length
1 <= n <= 10⁵
s1 and s2 consist only of lowercase English letters.

Hint:

Characters in two positions can be swapped if and only if the two positions have the same parity.
To be able to make the two strings equal, the characters at even and odd positions in the strings should be the same.

Solution:

The problem asks whether two strings of equal length can be made identical by repeatedly swapping characters whose indices differ by an even number. The solution recognizes that swaps are only possible between positions of the same parity (both even or both odd). Therefore, the multiset of characters at even indices in s1 must match that in s2, and similarly for odd indices. The PHP implementation counts character frequencies separately for even and odd positions in both strings and compares the frequency arrays.

Approach:

Observe that the allowed operation swaps characters at positions i and j when j - i is even, which means i and j have the same parity (both even or both odd).
Therefore, characters can be rearranged freely within the even‑index group and within the odd‑index group, but characters cannot move between groups.
To make s1 equal to s2, the multiset of characters at even positions in s1 must be exactly the same as the multiset of characters at even positions in s2, and likewise for odd positions.
The solution initialises four fixed‑size arrays (26 counters for each parity in each string).
It iterates through the strings once, incrementing the appropriate counter for each character based on its index parity.
Finally, it checks if the even‑count arrays are identical and the odd‑count arrays are identical.

Let's implement this solution in PHP: 2840. Check if Strings Can be Made Equal With Operations II

<?php
/**
 * @param String $s1
 * @param String $s2
 * @return Boolean
 */
function checkStrings(string $s1, string $s2): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo checkStrings("abcdba", "cabdab") . "\n";           // Output: true
echo checkStrings("abe", "bea") . "\n";                 // Output: false
echo checkStrings(["abc", "cba") . "\n";                // Output: true
?>

Explanation:

Parity groups: Swapping only allowed between indices of the same parity partitions the string into two independent groups: even indices (0,2,4,…) and odd indices (1,3,5,…).
Character counting: By counting character frequencies separately for each group, we capture exactly what multiset of letters can be formed in that group after any sequence of swaps.
Comparison: If the frequency vectors for even positions in s1 and s2 match, and the vectors for odd positions also match, then we can reorder each group independently to make the strings equal. Otherwise, it is impossible.
Efficiency: The counting is done in a single pass, using only O(1) extra space because the alphabet size is fixed (26 lowercase letters).
Edge cases: If a string length is 1, there is only one parity group; the logic still holds because the other group will have zero counts.

Complexity

Time Complexity: O(n), where n is the length of the strings. A single pass with constant‑time operations per character.
Space Complexity: O(1), since only four arrays of size 26 are used, independent of the input size.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

2839. Check if Strings Can be Made Equal With Operations I

MD ARIFUL HAQUE — Sun, 29 Mar 2026 17:59:16 +0000

2839. Check if Strings Can be Made Equal With Operations I

Difficulty: Easy

Topics: Mid Level, String, Biweekly Contest 112

You are given two strings s1 and s2, both of length 4, consisting of lowercase English letters.

You can apply the following operation on any of the two strings any number of times:

Choose any two indices i and j such that j - i = 2, then swap the two characters at those indices in the string.

Return true if you can make the strings s1 and s2 equal, and false otherwise.

Example 1:

Input: s1 = "abcd", s2 = "cdab"
Output: true
Explanation: We can do the following operations on s1:
- Choose the indices i = 0, j = 2. The resulting string is s1 = "cbad".
- Choose the indices i = 1, j = 3. The resulting string is s1 = "cdab" = s2.

Example 2:

Input: s1 = "abcd", s2 = "dacb"
Output: false
Explanation: It is not possible to make the two strings equal.

Example 3:

Input: s1 = "abab", s2 = "abab"
Output: true

Example 4:

Input: s1 = "abcd", s2 = "acbd"
Output: false

Constraints:

s1.length == s2.length == 4
s1 and s2 consist only of lowercase English letters.

Hint:

Since the strings are very small you can try a brute-force approach.
There are only 2 different swaps that are possible in a string.

Solution:

To determine whether two strings s1 and s2 (each of length 4) can be made equal using the allowed operation (swapping characters at indices where j - i = 2), we observe a key constraint:

You can only swap:
- Index 0 with 2
- Index 1 with 3 This means:
Characters at even indices (0,2) can only rearrange among themselves.
Characters at odd indices (1,3) can only rearrange among themselves. So, the problem reduces to checking whether:
The even-index characters of both strings match (after sorting), and
The odd-index characters of both strings match (after sorting). If both conditions are satisfied → return true, otherwise false.

Approach:

Extract characters at:
- Even indices (0, 2) from both strings.
- Odd indices (1, 3) from both strings.
Sort both even-index arrays.
Sort both odd-index arrays.
Compare:
- Even-index arrays of s1 and s2
- Odd-index arrays of s1 and s2
Return true if both match; otherwise return false.

Let's implement this solution in PHP: 2839. Check if Strings Can be Made Equal With Operations I

<?php
/**
 * @param String $s1
 * @param String $s2
 * @return Boolean
 */
function canBeEqual(string $s1, string $s2): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo canBeEqual("abcd", "cdab") . "\n";             // Output: true
echo canBeEqual("abcd", "dacb") . "\n";             // Output: false
echo canBeEqual("abab", "abab") . "\n";             // Output: true
echo canBeEqual("abcd", "acbd") . "\n";             // Output: false
?>

Explanation:

Only two swaps are possible:
- Swap index 0 ↔ 2
- Swap index 1 ↔ 3
This creates two independent groups:
- Even positions group
- Odd positions group
We cannot move characters between even and odd positions.
Therefore:
- The multiset (frequency) of even-index characters must match.
- The multiset (frequency) of odd-index characters must match.
Sorting both groups makes comparison easy.
If both sorted groups are equal → transformation is possible.

Complexity

Time Complexity: O(1), String length is fixed at 4, sorting 2 elements is constant time.
Space Complexity: O(1), Only small fixed-size arrays are used.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

2573. Find the String with LCP

MD ARIFUL HAQUE — Sat, 28 Mar 2026 15:42:34 +0000

2573. Find the String with LCP

Difficulty: Hard

Topics: Senior Staff, Array, String, Dynamic Programming, Greedy, Union-Find, Matrix, Weekly Contest 333

We define the lcp matrix of any 0-indexed string word of n lowercase English letters as an n x n grid such that:

lcp[i][j] is equal to the length of the longest common prefix between the substrings word[i,n-1] and word[j,n-1].

Given an n x n matrix lcp, return the alphabetically smallest string word that corresponds to lcp. If there is no such string, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example, "aabd" is lexicographically smaller than "aaca" because the first position they differ is at the third letter, and 'b' comes before 'c'.

Example 1:

Input: lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]
Output: "abab"
Explanation: lcp corresponds to any 4 letter string with two alternating letters. The lexicographically smallest of them is "abab".

Example 2:

Input: lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]
Output: "aaaa"
Explanation: lcp corresponds to any 4 letter string with a single distinct letter. The lexicographically smallest of them is "aaaa".

Example 3:

Input: lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]
Output: ""
Explanation: lcp[3][3] cannot be equal to 3 since word[3,...,3] consists of only a single letter; Thus, no answer exists.

Constraints:

1 <= n == lcp.length == lcp[i].length <= 1000
0 <= lcp[i][j] <= n

Hint:

Use the LCP array to determine which groups of elements must be equal.
Match the smallest letter to the group that contains the smallest unassigned index.
Build the LCP matrix of the resulting string then check if it is equal to the target LCP.

Solution:

The solution reconstructs the lexicographically smallest string from a given LCP (Longest Common Prefix) matrix. It first verifies necessary conditions (diagonal values, symmetry, bounds, and recursive LCP properties). Using a union‑find data structure, it groups indices that must share the same character (where lcp[i][j] > 0). It then enforces that indices with lcp[i][j] == 0 or where the characters after a common prefix must differ belong to distinct groups. The groups are assigned letters in the order of their first occurrence, always picking the smallest possible letter that does not conflict with already assigned groups. Finally, it builds the string and verifies it against the original LCP matrix, returning the string if valid, otherwise an empty string.

Approach:

Input validation
- Check that diagonal entries equal the suffix length: lcp[i][i] == n - i.
- Ensure symmetry: lcp[i][j] == lcp[j][i].
- Verify each entry does not exceed the maximum possible common prefix length: lcp[i][j] <= min(n-i, n-j).
- Enforce the recursive LCP condition: if lcp[i][j] > 0, then lcp[i+1][j+1] == lcp[i][j] - 1.
Union‑Find for character equality
- Union indices i and j whenever lcp[i][j] > 0 (they must start with the same character).
Conflict checks
- If lcp[i][j] == 0, then i and j must belong to different groups (first characters differ).
- If lcp[i][j] = k > 0 and i+k and j+k are inside the string, then word[i+k] != word[j+k]. Hence their groups must be different.
Group assignment & letter selection
- Map each index to its compressed group id, then order groups by the smallest index they contain.
- Assign letters to groups in that order, always picking the smallest unused letter that does not conflict with any neighbor group (groups that must be different).
String construction and verification
- Build the string by placing the assigned letter for each group at every index belonging to that group.
- Compute the LCP matrix of the constructed string and compare it with the input. Return the string if they match, otherwise an empty string.

Let's implement this solution in PHP: 2573. Find the String with LCP

<?php
/**
 * @param Integer[][] $lcp
 * @return String
 */
function findTheString(array $lcp): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo findTheString([[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]) . "\n";           // Output: "abab"
echo findTheString([[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]) . "\n";           // Output: "aaaa"
echo findTheString([[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]) . "\n";           // Output: ""
?>

Explanation:

Why the diagonal check? The LCP of a suffix with itself is the entire suffix, so lcp[i][i] must be exactly the length of that suffix (n - i).
Why the recursive condition? If two suffixes share a common prefix of length k > 0, then the suffixes starting one position later share a common prefix of length k-1. This gives a direct relation between adjacent entries.
Union‑Find groups: When lcp[i][j] >= 1, the first characters are equal, so indices i and j must have the same letter. Union‑Find efficiently collects all indices that are forced to be equal.
Conflict conditions
- lcp[i][j] == 0 → first characters differ, so i and j cannot be in the same group.
- lcp[i][j] = k > 0 → the characters at i+k and j+k must differ (otherwise the common prefix would be longer), so they must be in different groups.
Letter assignment order: To obtain the lexicographically smallest string, groups are processed in increasing order of their smallest index. For each group, we assign the smallest letter that is not already used by any group it must differ from (ensuring the string is minimal).
Final verification: Even after satisfying all necessary conditions, a constructed string might still produce a different LCP matrix due to subtle interactions. Therefore, we explicitly compute its LCP matrix and compare it to the input, rejecting any mismatch.

Complexity

Time Complexity: O(n²)
- All matrix checks run in O(n²).
- Union‑Find operations are nearly constant; total unions and finds are O(n²).
- Group assignment and letter selection involve scanning the matrix a few more times, still O(n²).
- The final verification also computes the LCP matrix in O(n²).
Space Complexity: O(n²)
- The input matrix is given; we store a copy for verification or use additional arrays for union‑find, groups, and adjacency lists (which in worst case can be O(n²)).
- The output string uses O(n) space.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

2946. Matrix Similarity After Cyclic Shifts

MD ARIFUL HAQUE — Fri, 27 Mar 2026 03:46:48 +0000

2946. Matrix Similarity After Cyclic Shifts

Difficulty: Easy

Topics: Mid Level, Array, Math, Matrix, Simulation, Weekly Contest 373

You are given an m x n integer matrix mat and an integer k. The matrix rows are 0-indexed.

The following process happens k times:

Even-indexed rows (0, 2, 4, ...) are cyclically shifted to the left.
Odd-indexed rows (1, 3, 5, ...) are cyclically shifted to the right.

Return true if the final modified matrix after k steps is identical to the original matrix, and false otherwise.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 4
Output: false
Explanation: In each step left shift is applied to rows 0 and 2 (even indices), and right shift to row 1 (odd index).

Example 2:

Input: mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2
Output: true
Explanation:

Example 3:

Input: mat = [[2,2],[2,2]], k = 3
Output: true
Explanation: As all the values are equal in the matrix, even after performing cyclic shifts the matrix will remain the same.

Example 4:

Input: mat = [[1,2],[3,4]], k = 0
Output: true

Example 4:

Input: mat = [[5],[7]], k = 5
Output: true

Constraints:

1 <= mat.length <= 25
1 <= mat[i].length <= 25
1 <= mat[i][j] <= 25
1 <= k <= 50

Hint:

You can reduce k shifts to (k % n) shifts as after n shifts the matrix will become similar to the initial matrix.

Solution:

The problem asks whether after performing k cyclic shifts on a matrix—even-indexed rows shifted left, odd-indexed rows shifted right—the matrix becomes identical to the original.

The solution reduces k modulo the number of columns (n) because a full cycle of n shifts brings any row back to its starting arrangement. It then checks that for every row and every column j, the element at j equals the element at (j + k) % n. This condition is necessary and sufficient for both left and right shifts to leave the row unchanged, and therefore for the whole matrix to be unchanged after k steps.

Approach:

Reduce k modulo n – Since shifting a row by n positions (left or right) returns it to the original order, we can replace k with k % n. If the result is 0, the matrix is already unchanged, so we return true.
Unified invariance check – For any row, being invariant under k left shifts is equivalent to being invariant under k right shifts. This reduces to verifying that for every column j, the element row[j] equals row[(j + k) % n].
Iterate over rows and columns – For each row, loop through all columns and test the condition. If any element fails, return false.
Return true – If all rows satisfy the condition, the matrix after k steps is identical to the original.

Let's implement this solution in PHP: 2946. Matrix Similarity After Cyclic Shifts

<?php
/**
 * @param Integer[][] $mat
 * @param Integer $k
 * @return Boolean
 */
function areSimilar(array $mat, int $k): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo areSimilar([[1,2,3],[4,5,6],[7,8,9]], 4) . "\n";               // Output: false
echo areSimilar([[1,2,1,2],[5,5,5,5],[6,3,6,3]], 2) . "\n";         // Output: true
echo areSimilar([[2,2],[2,2]], 3) . "\n";                           // Output: true
echo areSimilar([[1,2],[3,4]], 0) . "\n";                           // Output: true
echo areSimilar([[5],[7]], 5) . "\n";                               // Output: true
?>

Explanation:

Why reduce k modulo n?

A cyclic shift by n positions (left or right) restores the original order of a row. Therefore, performing k shifts is equivalent to performing k % n shifts. This simplification avoids unnecessary work and handles large k efficiently.
Why is the same condition used for both even and odd rows?
- For an even row (left shift): after k left shifts, the element originally at index j moves to index (j - k) mod n. For the row to be unchanged, we need mat[i][j] == mat[i][(j + k) mod n] (substituting j with (j + k) mod n).
- For an odd row (right shift): after k right shifts, the element originally at index j moves to index (j + k) mod n. For the row to be unchanged, we need mat[i][j] == mat[i][(j - k) mod n].
- The two conditions are equivalent because mat[i][j] == mat[i][(j + k) mod n] for all j implies mat[i][(j - k) mod n] == mat[i][j]. Thus, checking row[j] == row[(j + k) % n] works for both shift directions.
When is the matrix unchanged?

The matrix is unchanged exactly when every row is unchanged after its respective shifts. The condition tested ensures that for each row, a shift by k positions (left or right) leaves the row identical. Because k is already reduced modulo n, this is sufficient.

Complexity

Time Complexity: O(m × n) – We examine each element of the matrix once.
Space Complexity: O(1) – Only a few integer variables are used, regardless of input size.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

3548. Equal Sum Grid Partition II

MD ARIFUL HAQUE — Thu, 26 Mar 2026 16:11:57 +0000

3548. Equal Sum Grid Partition II

Difficulty: Hard

Topics: Principal, Array, Hash Table, Matrix, Enumeration, Prefix Sum, Weekly Contest 449

You are given an m x n matrix grid of positive integers. Your task is to determine if it is possible to make either one horizontal or one vertical cut on the grid such that:

Each of the two resulting sections formed by the cut is non-empty.
The sum of elements in both sections is equal, or can be made equal by discounting at most one single cell in total (from either section).
If a cell is discounted, the rest of the section must remain connected.

Return true if such a partition exists; otherwise, return false.

Note: A section is connected if every cell in it can be reached from any other cell by moving up, down, left, or right through other cells in the section.

Example 1:

Input: grid = [[1,4],[2,3]]
Output: true
Explanation:
- A horizontal cut after the first row gives sums 1 + 4 = 5 and 2 + 3 = 5, which are equal. Thus, the answer is true.

Example 2:

Input: grid = [[1,2],[3,4]]
Output: true
Explanation:
- A vertical cut after the first column gives sums 1 + 3 = 4 and 2 + 4 = 6.
- By discounting 2 from the right section (6 - 2 = 4), both sections have equal sums and remain connected. Thus, the answer is true.

Example 3:

Input: grid = [[1,2,4],[2,3,5]]
Output: false
Explanation:
- A horizontal cut after the first row gives 1 + 2 + 4 = 7 and 2 + 3 + 5 = 10.
- By discounting 3 from the bottom section (10 - 3 = 7), both sections have equal sums, but they do not remain connected as it splits the bottom section into two parts ([2] and [5]). Thus, the answer is false.

Example 4:

Input: grid = [[5]]
Output: true

Example 5:

Input: grid = [[1,3],[4,2]]
Output: true

Constraints:

1 <= m == grid.length <= 10⁵
1 <= n == grid[i].length <= 10⁵
2 <= m * n <= 10⁵
1 <= grid[i][j] <= 10⁵

Hint:

In a grid (or any subgrid), when can a section be disconnected? Can disconnected components occur if the section spans more than one row and more than one column?
Handle single rows or single columns separately. For all other partitions, maintain the sums and value frequencies of each section to check whether removing at most one element from one section can make the two sums equal.

Solution:

The solution determines whether a single horizontal or vertical cut can partition the grid into two non‑empty sections whose sums are either equal or can be made equal by discarding at most one cell, provided the remainder of each section stays connected. It uses prefix sums to compute section totals and frequency maps to check for a removable cell that balances the sums. Connectivity is only a concern when a section is a single row or column; in those cases the discounted cell must be at an end.

Approach:

Compute the total sum of all elements and a frequency map of all values.
Horizontal cuts: For each cut after row i-1, maintain the sum of the top part (S1) and the bottom part (S2) using row prefix sums. Also maintain frequency maps of values in the top and bottom parts.
- If S1 == S2, return true.
- If S1 > S2, let v = S1 - S2. If v exists in the top part’s frequency map, check whether the top part is either:
  - a single row (then v must be in the first or last column of that row), or
  - a single column (then v must be in the first or last row of that column), or
  - a rectangle with at least two rows and two columns (then any occurrence of v works). If the condition passes, return true.
- If S2 > S1, similarly check the bottom part.
Vertical cuts: Analogous processing using column prefix sums and frequency maps for left and right parts.
If no cut satisfies the condition, return false.

Let's implement this solution in PHP: 3548. Equal Sum Grid Partition II

<?php
/**
 * @param Integer[][] $grid
 * @return Boolean
 */
function canPartitionGrid(array $grid): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo canPartitionGrid([[1,4],[2,3]]) . "\n";            // Output: true
echo canPartitionGrid([[1,2],[3,4]]) . "\n";            // Output: true
echo canPartitionGrid([[1,2,4],[2,3,5]]) . "\n";        // Output: false
echo canPartitionGrid([[5]]) . "\n";                    // Output: true
echo canPartitionGrid([[1,3],[4,2]]) . "\n";            // Output: true
?>

Explanation:

Prefix sums allow O(1) retrieval of section totals after O(m·n) preprocessing.
Frequency maps let us quickly test whether a value that would balance the sums is present in the larger section.
Connectivity is automatically guaranteed for sections with both dimensions ≥ 2 when a single cell is removed. For single‑row or single‑column sections, the removed cell must be at an extremity to keep the rest connected.
The algorithm checks every possible horizontal and vertical cut, stopping as soon as a valid one is found.

Complexity

Time Complexity: O(m·n) – each cell is processed a constant number of times (prefix sums, frequency updates, and checks).
Space Complexity: O(m·n) – to store the grid and frequency maps, but since the total number of cells ≤ 10⁵, this is acceptable.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub