DEV Community: MD ARIFUL HAQUE

1096. Brace Expansion II

MD ARIFUL HAQUE — Fri, 25 Sep 2026 20:08:53 +0000

1096. Brace Expansion II

Difficulty: Hard

Topics: Principal, Hash Table, String, Backtracking, Stack, Breadth-First Search, Sorting, Weekly Contest 142

Under the grammar given below, strings can represent a set of lowercase words. Let R(expr) denote the set of words the expression represents.

The grammar can best be understood through simple examples:

Single letters represent a singleton set containing that word.
- R("a") = {"a"}
- R("w") = {"w"}
When we take a comma-delimited list of two or more expressions, we take the union of possibilities.
- R("{a,b,c}") = {"a","b","c"}
- R("{{a,b},{b,c}}") = {"a","b","c"} (notice the final set only contains each word at most once)
When we concatenate two expressions, we take the set of possible concatenations between two words where the first word comes from the first expression and the second word comes from the second expression.
- R("{a,b}{c,d}") = {"ac","ad","bc","bd"}
- R("a{b,c}{d,e}f{g,h}") = {"abdfg", "abdfh", "abefg", "abefh", "acdfg", "acdfh", "acefg", "acefh"}

Formally, the three rules for our grammar:

For every lowercase letter x, we have R(x) = {x}.
For expressions e₁, e₂, ... , eₖ with k >= 2, we have R({e₁, e₂, ...}) = R(e₁) ∪ R(e₂) ∪ ...
For expressions e₁ and e₂, we have R(e₁ + e₂) = {a + b for (a, b) in R(e₁) × R(e₂)}, where + denotes concatenation, and × denotes the cartesian product.

Given an expression representing a set of words under the given grammar, return the sorted list of words that the expression represents.

Example 1:

Input: expression = "{a,b}{c,{d,e}}"
Output: ["ac","ad","ae","bc","bd","be"]

Example 2:

Input: expression = "{{a,z},a{b,c},{ab,z}}"
Output: ["a","ab","ac","z"]
Explanation: Each distinct word is written only once in the final answer.

Example 3:

Input: expression = "a{b,c}{d,e}f{g,h}"
Output: ["abdfg","abdfh","abefg","abefh","acdfg","acdfh","acefg","acefh"]

Example 4:

Input: expression = "a"
Output: ["a"]

Example 5:

Input: expression = {a,b,c}
Output: ["a","b","c"]

Example 6:*

Input: expression = "{{a,b},{b,c}}"
Output: ["a","b","c"]

Example 7:

Input: expression = "x{a,b}y"
Output: ["xay","xby"]

Example 8:

Input: expression = "{{a,b},c{d,e}}"
Output: ["a","b","cd","ce"]

Example 9:

Input: expression = "{a,b}{c,d}"
Output: ["ac","ad","bc","bd"]

Example 10:

Input: expression = "{a,b}{c,d}{e,f}"
Output: ["ace","acf","ade","adf","bce","bcf","bde","bdf"]

Constraints:

1 <= expression.length <= 60
expression[i] consists of '{', '}', ','or lowercase English letters.
The given expression represents a set of words based on the grammar given in the description.

Hint:

You can write helper methods to parse the next "chunk" of the expression. If you see eg. "a", the answer is just the set {a}. If you see "{", you parse until you complete the "}" (the number of { and } seen are equal) and that becomes a chunk that you find where the appropriate commas are, and parse each individual expression between the commas.

Similar Questions:

1087. Brace Expansion

Solution:

We solve the brace expansion by recursively parsing the expression as sets of strings. Concatenation is handled with a Cartesian product, while comma-separated alternatives inside {...} are merged as a union. Associative arrays are used as sets to remove duplicates immediately, and the final result is sorted.

Approach

Use a recursive descent parser with a shared index $i into the expression string.
parseAlternative($i) parses a concatenation sequence until it sees ,, }, or the end of the string.
Start each concatenation sequence with ['' => true], the identity for concatenation.
When encountering {, recursively parse each comma-separated alternative and union them into a $termSet.
When encountering a lowercase letter, treat it as a singleton term.
Concatenate the current prefix set with the parsed term set using Cartesian product.
Store generated words as array keys, e.g. $next[$left . $right] = true, to deduplicate.
At the top level, call the parser, then sort() the final unique words.

Let's implement this solution in PHP: 1096. Brace Expansion II

<?php
function braceExpansionII(string $expression): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Parse a concatenated expression until ',' or '}' or end of string.
 */
function parseAlternative(string $s, int &$i, int $n): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo braceExpansionII("{a,b}{c,{d,e}}") .  "\n";                // Output: ["ac","ad","ae","bc","bd","be"]
echo braceExpansionII("{{a,z},a{b,c},{ab,z}}") .  "\n";         // Output: ["a","ab","ac","z"]
echo braceExpansionII("a{b,c}{d,e}f{g,h}") .  "\n";                 // Output: ["abdfg","abdfh","abefg","abefh","acdfg","acdfh","acefg","acefh"]
echo braceExpansionII("a") .  "\n";                                 // Output: ["a"]
echo braceExpansionII("{a,b,c}") .  "\n";                           // Output: ["a","b","c"]
echo braceExpansionII("{{a,b},{b,c}}") .  "\n";                 // Output: ["a","b","c"]
echo braceExpansionII("x{a,b}y") .  "\n";                           // Output: ["xay","xby"]
echo braceExpansionII("{{a,b},c{d,e}}") .  "\n";                // Output: ["a","b","cd","ce"]
echo braceExpansionII("{a,b}{c,d}") .  "\n";                    // Output: ["ac","ad","bc","bd"]
echo braceExpansionII("{a,b}{c,d}{e,f}") .  "\n";               // Output: ["ace","acf","ade","adf","bce","bcf","bde","bdf"]
?>

Explanation:

The helper method stops naturally at , and }, which makes it suitable for parsing one alternative at a time inside braces.
Nested braces work automatically because { triggers another recursive call.
The $termSet represents the union of all alternatives inside a brace group.
The $set represents all possible concatenations parsed so far in the current sequence.
Starting with '' ensures the first term is simply concatenated onto an empty prefix.
Using word => true removes duplicates during both union and concatenation.
The final array_keys() converts the set back into a list of words, and sort() gives the required lexicographical order.

Complexity Analysis

Let n be the expression length and W be the number of distinct output words.
The output size W can be exponential in n, since brace expansion can generate many combinations.
Time: parsing is O(n), but combination generation depends on output size. Ignoring string-copy costs, it is roughly O(n * W). Including string concatenation costs, up to O(n² * W).
Space: O(n * W) for stored intermediate/final words, plus O(n) recursion depth. Including full string storage, up to O(n² * W) 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

3550. Smallest Index With Digit Sum Equal to Index

MD ARIFUL HAQUE — Thu, 24 Sep 2026 16:48:46 +0000

3550. Smallest Index With Digit Sum Equal to Index

Difficulty: Easy

Topics: Mid Level, Array, Math, Weekly Contest 450

You are given an integer array nums.

Return the smallest index i such that the sum of the digits of nums[i] is equal to i.

If no such index exists, return -1.

Example 1:

Input: nums = [1,3,2]
Output: 2
Explanation: For nums[2] = 2, the sum of digits is 2, which is equal to index i = 2. Thus, the output is 2.

Example 2:

Input: nums = [1,10,11]
Output: 1
Explanation:
- For nums[1] = 10, the sum of digits is 1 + 0 = 1, which is equal to index i = 1.
- For nums[2] = 11, the sum of digits is 1 + 1 = 2, which is equal to index i = 2.
- Since index 1 is the smallest, the output is 1.

Example 3:

Input: nums = [1,2,3]
Output: -1
Explanation: Since no index satisfies the condition, the output is -1.

Example 4:

Input: nums = [0]
Output: 0

Example 5:

Input: nums = [0, 1]
Output: 0

Example 6:

Input: nums = [9, 10]
Output: 1

Example 7:

Input: nums = [5, 6, 7, 8, 9, 10]
Output: 5

Example 8:

Input: nums = [1000]
Output: -1

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

Hint:

Simulate as described

Solution:

We scan the array from left to right, compute the sum of digits for each nums[i], and return the first index i where that digit sum equals i. If no index satisfies the condition, we return -1.

Approach

Iterate through nums using foreach ($nums as $i => $num).
For each number, compute its digit sum by repeatedly taking % 10 and dividing by 10.
Compare the computed digit sum with the current index i.
Return i immediately when a match is found, because scanning left-to-right guarantees the smallest index.
If the loop finishes without a match, return -1.

Let's implement this solution in PHP: 3550. Smallest Index With Digit Sum Equal to Index

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

// Test cases
echo smallestIndex([1,3,2]) .  "\n";                    // Output: 2
echo smallestIndex([1,10,11]) .  "\n";                  // Output: 1
echo smallestIndex([1,2,3]) .  "\n";                    // Output: -1
echo smallestIndex([0]) .  "\n";                        // Output: 0
echo smallestIndex([0,1]) .  "\n";                      // Output: 0
echo smallestIndex([9,10]) .  "\n";                     // Output: 1
echo smallestIndex([5, 6, 7, 8, 9, 10]) .  "\n";        // Output: 5
echo smallestIndex([1000]) .  "\n";                     // Output: -1
?>

Explanation:

Index i starts from 0.
For a number like 10, the digit sum is 1 + 0 = 1.
For nums[i] = 0, the digit sum is 0, which is handled correctly because the while ($x > 0) loop simply does not run.
Since we return on the first valid index, no extra comparison or storage is needed.

Complexity Analysis

Time Complexity: O(n * d), where n is the length of nums and d is the maximum number of digits in nums[i]. Since nums[i] <= 1000, d <= 4, so this is effectively O(n).
Space Complexity: O(1), because only a few integer variables 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

1658. Minimum Operations to Reduce X to Zero

MD ARIFUL HAQUE — Wed, 23 Sep 2026 15:59:06 +0000

1658. Minimum Operations to Reduce X to Zero

Difficulty: Medium

Topics: Staff, Array, Hash Table, Binary Search, Sliding Window, Prefix Sum, Weekly Contest 215

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it is possible, otherwise, return -1.

Example 1:

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

Example 2:

Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:

Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

Example 4:

Input: nums = [1,2,3], x = 6
Output: 3

Example 5:

Input: nums = [1,2,3], x = 3
Output: 1

Example 6:

Input: nums = [1,2,3], x = 4
Output: 2

Example 7:

Input: nums = [1,1,1,1], x = 2
Output: 2

Example 8:

Input: nums = [1,2,3,4,5], x = 15
Output: 5

Example 9:

Input: nums = [1,2,3,4,5], x = 100
Output: -1

Example 10:

Input: nums = [2], x = 2
Output: 1

Example 11:

Input: nums = [2], x = 3
Output: -1

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴
1 <= x <= 10⁹

Hint:

Think in reverse; instead of finding the minimum prefix + suffix, find the maximum subarray.
Finding the maximum subarray is standard and can be done greedily.

Solution:

We solve this by reversing the problem: removing elements from both ends with sum x is equivalent to keeping one contiguous middle subarray with sum total - x. So we find the longest middle subarray whose sum is total - x using a sliding window. The minimum operations is then n - maxLength, or -1 if no such subarray exists.

Approach

Compute total = array_sum(nums).
Set target = total - x.
If target < 0, return -1 because even removing all elements cannot reduce x to zero.
If target == 0, return n because all elements must be removed.
Use a sliding window with left, right, and sum.
Expand right and add nums[right] to sum.
While sum > target, shrink the window from left.
When sum == target, update the maximum middle subarray length.
Return n - maxLength if maxLength > 0; otherwise return -1.

Let's implement this solution in PHP: 1658. Minimum Operations to Reduce X to Zero

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

// Test cases
echo minOperations([1,1,4,2,3], 5) .  "\n";         // Output: 2
echo minOperations([5,6,7,8,9], 4) .  "\n";         // Output: -1
echo minOperations([3,2,20,1,1,3], 10) .  "\n";     // Output: 5
echo minOperations([1,2,3], 6) .  "\n";             // Output: 3
echo minOperations([1,2,3], 3) .  "\n";             // Output: 1
echo minOperations([1,2,3], 4) .  "\n";             // Output: 2
echo minOperations([1,1,1,1], 2) .  "\n";           // Output: 2
echo minOperations([1,2,3,4,5], 15) .  "\n";        // Output: 5
echo minOperations([1,2,3,4,5], 100) .  "\n";       // Output: -1
echo minOperations([2], 2) .  "\n";                 // Output: 1
echo minOperations([2], 3) .  "\n";                 // Output: -1
?>

Explanation:

Each operation removes either the leftmost or rightmost element.
After all operations, the remaining untouched elements form a contiguous subarray in the middle.
The removed elements must sum to x.
Therefore, the kept middle subarray must sum to total - x.
Minimizing operations means maximizing the length of this kept middle subarray.
Since all nums[i] are positive, a sliding window can efficiently find the longest subarray with the required sum.
If no such subarray exists, it is impossible to reduce x to exactly 0.

Complexity Analysis

Time Complexity: O(n) — each element is added to and removed from the sliding window at most once.
Space Complexity: O(1) — only a few variables 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

3535. Find X Value of Array II

MD ARIFUL HAQUE — Tue, 22 Sep 2026 16:04:11 +0000

3535. Find X Value of Array II

Difficulty: Hard

Topics: Senior Staff, Array, Math, Segment Tree, Weekly Contest 446

You are given an array of positive integers nums and a positive integer k. You are also given a 2D array queries, where queries[i] = [indexᵢ, valueᵢ, startᵢ, xᵢ].

You are allowed to perform an operation once on nums, where you can remove any suffix from nums such that nums remains non-empty.

The x-value of nums for a given x is defined as the number of ways to perform this operation so that the product of the remaining elements leaves a remainder of x modulo k.

For each query in queries you need to determine the x-value of nums for xᵢ after performing the following actions:

Update nums[indexᵢ] to valueᵢ. Only this step persists for the rest of the queries.
Remove the prefix nums[0..(startᵢ - 1)] (where nums[0..(-1)] will be used to represent the empty prefix).

Return an array result of size queries.length where result[i] is the answer for the iᵗʰ query.

A prefix of an array is a subarray[^1] that starts from the beginning of the array and extends to any point within it.

A suffix of an array is a subarray[^1] that starts at any point within the array and extends to the end of the array.

Note that the prefix and suffix to be chosen for the operation can be empty.

Note that x-value has a different definition in this version.

Example 1:

Input: nums = [1,2,3,4,5], k = 3, queries = [[2,2,0,2],[3,3,3,0],[0,1,0,1]]
Output: [2,2,2]
Explanation:
- For query 0, nums becomes [1, 2, 2, 4, 5], and the empty prefix must be removed. The possible operations are:
- Remove the suffix [2, 4, 5]. nums becomes [1, 2].
- Remove the empty suffix. nums becomes [1, 2, 2, 4, 5] with a product 80, which gives remainder 2 when divided by 3.
- For query 1, nums becomes [1, 2, 2, 3, 5], and the prefix [1, 2, 2] must be removed. The possible operations are:
- Remove the empty suffix. nums becomes [3, 5].
- Remove the suffix [5]. nums becomes [3].
- For query 2, nums becomes [1, 2, 2, 3, 5], and the empty prefix must be removed. The possible operations are:
- Remove the suffix [2, 2, 3, 5]. nums becomes [1].
- Remove the suffix [3, 5]. nums becomes [1, 2, 2].

Example 2:

Input: nums = [1,2,4,8,16,32], k = 4, queries = [[0,2,0,2],[0,2,0,1]]
Output: [1,0]
Explanation:
- For query 0, nums becomes [2, 2, 4, 8, 16, 32]. The only possible operation is:
- Remove the suffix [2, 4, 8, 16, 32].
- For query 1, nums becomes [2, 2, 4, 8, 16, 32]. There is no possible way to perform the operation.

Example 3:

Input: nums = [1,1,2,1,1], k = 2, queries = [[2,1,0,1]]
Output: [5]

Example 4:

Input: nums = [5], k = 2, queries = [[0,1,0,1]]
Output: [1]

Example 5:

Input: nums = [2,2], k = 3, queries = [[0,2,0,0]]
Output: [0]

Example 6:

Input: nums = [1,2,3], k = 2, queries = [[1,2,0,0],[1,1,0,1]]
Output: [2,3]

Constraints:

1 <= nums[i] <= 10⁹
1 <= nums.length <= 10⁵
1 <= k <= 5
1 <= queries.length <= 2 * 10⁴
queries[i] == [indexᵢ, valueᵢ, startᵢ, xᵢ]
0 <= indexᵢ <= nums.length - 1
1 <= valueᵢ <= 10⁹
0 <= startᵢ <= nums.length - 1
0 <= xᵢ <= k - 1

Hint:

Use a segment tree to efficiently maintain and merge product prefix information for the array nums.
In each segment tree node, store a frequency count of prefix product remainders for every x in the range [0, k - 1].
For each query, update nums[index] to value, then merge the segments corresponding to nums[start..n - 1] to compute the x-value for xᵢ.

Solution:

We maintain a segment tree where each node stores the product modulo k of its segment and a frequency array of non-empty prefix product remainders. After each point update, a range query over nums[start..n-1] merges segment nodes in order, and the answer is the frequency of remainder x.

Approach

Removing prefix nums[0..start-1] leaves the subarray nums[start..n-1].
Removing a suffix while keeping the array non-empty is equivalent to choosing a non-empty prefix of this remaining subarray.
So the task becomes: count non-empty prefixes of nums[start..n-1] whose product modulo k equals x.
Each segment-tree node stores:
- prod: product of the whole segment modulo k.
- cnt[r]: number of non-empty prefixes of this segment whose product modulo k is r.
Merge two adjacent segments L then R:
- New product = prodL * prodR % k.
- Prefixes are either from L, or the whole L followed by a prefix of R.
- For every remainder y with cntR[y] > 0, add it to remainder (prodL * y) % k.
Build the tree bottom-up.
For each query:
- Update nums[index] = value in the tree and recompute ancestors.
- Query range [start, n - 1] by merging segment nodes in left-to-right order.
- Return mergedCnt[x].

Let's implement this solution in PHP: 3535. Find X Value of Array II

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

/**
 * @param $prod
 * @param $cnt
 * @param $i
 * @param $k
 * @return void
 */
function pull(&$prod, &$cnt, $i, $k): void
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $leftProd
 * @param $leftCnt
 * @param $rightProd
 * @param $rightCnt
 * @param $k
 * @return void
 */
function mergeLeft(&$leftProd, &$leftCnt, $rightProd, $rightCnt, $k): void
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $nodeProd
 * @param $nodeCnt
 * @param $rightProd
 * @param $rightCnt
 * @param $k
 * @return void
 */
function mergeRight($nodeProd, $nodeCnt, &$rightProd, &$rightCnt, $k): void
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo resultArray([1,2,3,4,5], 3, [[2,2,0,2],[3,3,3,0],[0,1,0,1]]) .  "\n";      // Output: [2, 2, 2]
echo resultArray([1,2,4,8,16,32], 4, [[0,2,0,2],[0,2,0,1]]) .  "\n";            // Output: [1, 0]
echo resultArray([1,1,2,1,1], 2, [[2,1,0,1]]) .  "\n";                          // Output: [5]
echo resultArray([5], 2, [[0,1,0,1]]) .  "\n";                                  // Output: [1]
echo resultArray([2,2], 3, [[0,2,0,0]]) .  "\n";                                // Output: [0]
echo resultArray([1,2,3], 2, [[1,2,0,0],[1,1,0,1]]) .  "\n";                    // Output: [2,3]
?>

Explanation:

The segment tree avoids recomputing prefix products from scratch for every query.
Since k <= 5, each merge only loops over at most 5 remainders, making merges very cheap.
The update is persistent because the tree is updated before processing the next query.
The range query preserves order using left and right accumulators:
- Left accumulator collects segments from the left side.
- Right accumulator collects segments from the right side.
- Finally, they are merged in the correct order.
The provided PHP code implements exactly this logic.

Complexity Analysis

Let n = nums.length, q = queries.length, and k <= 5.
Build: O(n * k)
Each update: O(k log n)
Each query: O(k log n)
Total time: O(k * (n + q log n))
Space: O(k * n) for the segment tree frequency arrays.

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

3524. Find X Value of Array I

MD ARIFUL HAQUE — Mon, 21 Sep 2026 10:08:19 +0000

3524. Find X Value of Array I

Difficulty: Medium

Topics: Staff, Array, Math, Dynamic Programming, Weekly Contest 446

You are given an array of positive integers nums, and a positive integer k.

You are allowed to perform an operation once on nums, where in each operation you can remove any non-overlapping prefix and suffix from nums such that nums remains non-empty.

You need to find the x-value of nums, which is the number of ways to perform this operation so that the product of the remaining elements leaves a remainder of x when divided by k.

Return an array result of size k where result[x] is the x-value of nums for 0 <= x <= k - 1.

A prefix of an array is a subarray¹ that starts from the beginning of the array and extends to any point within it.

A suffix of an array is a subarray¹ that starts at any point within the array and extends to the end of the array.

Note that the prefix and suffix to be chosen for the operation can be empty.

Example 1:

Input: nums = [1,2,3,4,5], k = 3
Output: [9,2,4]
Explanation:
- For x = 0, the possible operations include all possible ways to remove non-overlapping prefix/suffix that do not remove nums[2] == 3.
- For x = 1, the possible operations are:
  - Remove the empty prefix and the suffix [2, 3, 4, 5]. nums becomes [1].
  - Remove the prefix [1, 2, 3] and the suffix [5]. nums becomes [4].
- For x = 2, the possible operations are:
  - Remove the empty prefix and the suffix [3, 4, 5]. nums becomes [1, 2].
  - Remove the prefix [1] and the suffix [3, 4, 5]. nums becomes [2].
  - Remove the prefix [1, 2, 3] and the empty suffix. nums becomes [4, 5].
  - Remove the prefix [1, 2, 3, 4] and the empty suffix. nums becomes [5].

Example 2:

Input: nums = [1,2,4,8,16,32], k = 4
Output: [18,1,2,0]
Explanation:
- For x = 0, the only operations that do not result in x = 0 are:
  - Remove the empty prefix and the suffix [4, 8, 16, 32]. nums becomes [1, 2].
  - Remove the empty prefix and the suffix [2, 4, 8, 16, 32]. nums becomes [1].
  - Remove the prefix [1] and the suffix [4, 8, 16, 32]. nums becomes [2].
- For x = 1, the only possible operation is:
  - Remove the empty prefix and the suffix [2, 4, 8, 16, 32]. nums becomes [1].
- For x = 2, the possible operations are:
  - Remove the empty prefix and the suffix [4, 8, 16, 32]. nums becomes [1, 2].
  - Remove the prefix [1] and the suffix [4, 8, 16, 32]. nums becomes [2].
- For x = 3, there is no possible way to perform the operation.

Example 3:

Input: nums = [1,1,2,1,1], k = 2
Output: [9,6]

Example 4:

Input: nums = [5], k = 3
Output: [0,0,1]

Example 5:

Input: nums = [1,1,1], k = 5
Output: [0,6,0,0,0]

Example 6:

Input: nums = [2,3,4], k = 1
Output: [6]

Constraints:

1 <= nums[i] <= 10⁹
1 <= nums.length <= 10⁵
1 <= k <= 5

Hint:

Use dynamic programming.
Define dp[i][r] as the count of subarrays ending at index i whose product modulo k equals r.
Compute dp[i][r] for each index i in nums and sum over all indices to get the final counts for each remainder.

Solution:

We treat every valid operation as choosing exactly one non-empty contiguous subarray to remain after removing a prefix and suffix. We count all such subarrays whose product modulo k equals each remainder x. This is done with a rolling DP over remainders modulo k, since k <= 5.

Approach

A valid operation is equivalent to selecting a non-empty subarray nums[l..r] to keep.
So the task becomes: count all non-empty contiguous subarrays by (product of subarray) % k.
Process nums from left to right.
Maintain dp[r]: number of subarrays ending at the previous index whose product modulo k is r.
For the current number num, let m = num % k.
New subarrays ending here are:
- The single-element subarray [num], giving remainder m.
- Every previous subarray extended by num, changing remainder from r to (r * m) % k.
Accumulate these counts into the final answer array.

Let's implement this solution in PHP: 3524. Find X Value of Array I

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

// Test cases
echo resultArray([1,2,3,4,5], 3) .  "\n";           // Output: [9,2,4]
echo resultArray([1,2,4,8,16,32], 4) .  "\n";       // Output: [18,1,2,0]
echo resultArray([1,1,2,1,1], 2) .  "\n";           // Output: [9,6]
echo resultArray([5], 3) .  "\n";                   // Output: [0,0,1]
echo resultArray([1,1,1], 5) .  "\n";               // Output: [0,6,0,0,0]
echo resultArray([2,3,4], 1) .  "\n";               // Output: [6]
?>

Explanation:

Initialize ans and dp as arrays of size k filled with 0.
For each num in nums:
- Compute m = num % k.
- Create next array of size k filled with 0.
- Add the single-element subarray: next[m] += 1.
- For every remainder r from 0 to k - 1:
  - If dp[r] > 0, extend those subarrays:
    - next[(r * m) % k] += dp[r]
- Add all counts in next to ans.
- Set dp = next.
Return ans, where ans[x] is the number of valid operations giving remainder x.

Complexity Analysis

Time Complexity: O(n * k) For each element, we iterate over k possible remainders. Since k <= 5, this is effectively O(n).
Space Complexity: O(k) We only store DP and answer arrays of size k.

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

Subarray: A subarray is a contiguous sequence of elements within an array. ↩

3498. Reverse Degree of a String

MD ARIFUL HAQUE — Sun, 20 Sep 2026 17:36:56 +0000

3498. Reverse Degree of a String

Difficulty: Easy

Topics: Mid Level, String, Simulation, Biweekly Contest 153

Given a string s, calculate its reverse degree.

The reverse degree is calculated as follows:

For each character, multiply its position in the reversed alphabet ('a' = 26, 'b' = 25, ..., 'z' = 1) with its position in the string (1-indexed).
Sum these products for all characters in the string.

Return the reverse degree of s.

Example 1:

Input: s = "abc"
Output: 148
Explanation:

Letter	Index in Reversed Alphabet	Index in String	Product
`'a'`	26	1	26
`'b'`	25	2	50
`'c'`	24	3	72

The reversed degree is 26 + 50 + 72 = 148.

Example 2:

Input: s = "zaza"
Output: 160
Explanation:

Letter	Index in Reversed Alphabet	Index in String	Product
`'z'`	1	1	1
`'a'`	26	2	52
`'z'`	1	3	3
`'a'`	26	4	104

The reverse degree is 1 + 52 + 3 + 104 = 160.

Example 3:

Input: s = "a"
Output: 26

Example 4:

Input: s = "z"
Output: 1

Example 5:

Input: s = "az"
Output: 28

Example 6:

Input: s = "za"
Output: 53

Example 7:

Input: s = "aaaa"
Output: 260

Example 8:

Input: s = "zzzz"
Output: 10

Constraints:

1 <= s.length <= 1000
s contains only lowercase English letters.

Hint:

Simulate the operations as described.

Solution:

We iterate through s, map each character to its reverse alphabet value, multiply by its 1-indexed position, and sum all products.

Approach

Initialize sum = 0.
Traverse s using a zero-based loop index $i.
Convert $i to the 1-based string position: $i + 1.
Convert the character to its reverse alphabet value:
- ord($s[$i]) - ord('a') gives 0 for 'a', 25 for 'z'.
- 26 - value gives 'a' -> 26, 'z' -> 1.
Add positionInString * positionInReversedAlphabet to $sum.
Return $sum.

Let's implement this solution in PHP: 3498. Reverse Degree of a String

<?php
/**
 * @param String $s
 * @return Integer
 */
function reverseDegree(string $s): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo reverseDegree("abc") . "\n";       // Output: 148
echo reverseDegree("zaza") . "\n";      // Output: 160
echo reverseDegree("a") . "\n";         // Output: 26
echo reverseDegree("z") . "\n";         // Output: 1
echo reverseDegree("az") . "\n";        // Output: 28
echo reverseDegree("za") . "\n";        // Output: 53
echo reverseDegree("aaaa") . "\n";      // Output: 260
echo reverseDegree("zzzz") . "\n";      // Output: 10
?>

Explanation:

'a' has reversed alphabet index 26.
'z' has reversed alphabet index 1.
For "abc": (1 * 26) + (2 * 25) + (3 * 24) = 26 + 50 + 72 = 148.
For "zaza": (1 * 1) + (2 * 26) + (3 * 1) + (4 * 26) = 1 + 52 + 3 + 104 = 160.
The solution directly simulates the problem definition, so no sorting or extra mapping array is needed.

Complexity Analysis

Time Complexity: O(n), where n = strlen(s), because each character is processed once.
Space Complexity: O(1), because only a few integer variables 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

1401. Circle and Rectangle Overlapping

MD ARIFUL HAQUE — Sat, 19 Sep 2026 12:34:31 +0000

1401. Circle and Rectangle Overlapping

Difficulty: Medium

Topics: Staff, Math, Geometry, Biweekly Contest 23

You are given a circle represented as (radius, xCenter, yCenter) and an axis-aligned rectangle represented as (x1, y1, x2, y2), where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the rectangle.

Return true if the circle and rectangle are overlapped otherwise return false. In other words, check if there is any point (xᵢ, yᵢ) that belongs to the circle and the rectangle at the same time.

Example 1:

Input: radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
Output: true
Explanation: Circle and rectangle share the point (1,0).

Example 2:

Input: radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
Output: false

Example 3:

Input: radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
Output: true

Example 4:

Input: radius = 2, xCenter = 0, yCenter = 0, x1 = -1, y1 = -1, x2 = 1, y2 = 1
Output: true

Example 5:

Input: radius = 1, xCenter = 10, yCenter = 10, x1 = 0, y1 = 0, x2 = 2, y2 = 2
Output: false

Example 6:

Input: radius = 5, xCenter = 0, yCenter = 0, x1 = 3, y1 = 4, x2 = 5, y2 = 5
Output: true

Example 7:

Input: radius = 2, xCenter = 0, yCenter = 0, x1 = 2, y1 = -1, x2 = 4, y2 = 1
Output: true

Example 8:

Input: radius = 1, xCenter = 0, yCenter = 0, x1 = 2, y1 = 0, x2 = 3, y2 = 1
Output: false

Constraints:

1 <= radius <= 2000
-10⁴ <= xCenter, yCenter <= 10⁴
-10⁴ <= x1 < x2 <= 10⁴
-10⁴ <= y1 < y2 <= 10⁴

Hint:

Locate the closest point of the square to the circle, you can then find the distance from this point to the center of the circle and check if this is less than or equal to the radius.

Solution:

We solve the circle-rectangle overlap problem by finding the point on the axis-aligned rectangle closest to the circle’s center. If that closest point is within the circle’s radius, the two shapes overlap. This gives an O(1) math/geometry solution.

Approach

Clamp the circle center’s x-coordinate to the rectangle’s x-range [x1, x2].
Clamp the circle center’s y-coordinate to the rectangle’s y-range [y1, y2].
The resulting point (closestX, closestY) is the nearest point on the rectangle to the circle center.
Compute the squared distance from the circle center to this closest point.
If the squared distance is less than or equal to radius², return true; otherwise return false.

Let's implement this solution in PHP: 1401. Circle and Rectangle Overlapping

<?php
/**
 * @param Integer $radius
 * @param Integer $xCenter
 * @param Integer $yCenter
 * @param Integer $x1
 * @param Integer $y1
 * @param Integer $x2
 * @param Integer $y2
 * @return Boolean
 */
function checkOverlap(int $radius, int $xCenter, int $yCenter, int $x1, int $y1, int $x2, int $y2): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo checkOverlap(1, 0, 0, 1, -1, 3, 1) .  "\n";        // Output: true
echo checkOverlap(1, 1, 1, 1, -3, 2, -1) .  "\n";       // Output: false
echo checkOverlap(1, 0, 0, -1, 0, 0, 1) .  "\n";        // Output: true
echo checkOverlap(2, 0, 0, -1, -1, 1, 1) .  "\n";       // Output: true
echo checkOverlap(1, 10, 10, 0, 0, 2, 2) .  "\n";       // Output: false
echo checkOverlap(5, 0, 0, 3, 4, 5, 5) .  "\n";         // Output: true
echo checkOverlap(2, 0, 0, 2, -1, 4, 1) .  "\n";        // Output: true
echo checkOverlap(1, 0, 0, 2, 0, 3, 1) .  "\n";         // Output: false
?>

Explanation:

If the circle center is inside the rectangle, the clamped point equals the center, so distance is 0, and the result is true.
If the circle center is outside the rectangle, the closest point lies on an edge or corner of the rectangle.
Using squared distance avoids floating-point operations and square roots.
Boundary touching counts as overlap, so the comparison uses <=.
This handles all cases: center inside, circle intersecting an edge, circle intersecting a corner, circle outside, and circle touching exactly.

Complexity Analysis

Time Complexity: O(1) — only a constant number of arithmetic and comparison operations.
Space Complexity: O(1) — no extra data structures 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

1520. Maximum Number of Non-Overlapping Substrings

MD ARIFUL HAQUE — Fri, 18 Sep 2026 14:34:01 +0000

1520. Maximum Number of Non-Overlapping Substrings

Difficulty: Hard

Topics: Senior Staff, Hash Table, String, Greedy, Sorting, Weekly Contest 198

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

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

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

Notice that you can return the substrings in any order.

Example 1:

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

Example 2:

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

Example 3:

Input: s = "abac"
Output: ["b","c"]

Example 4:

Input: s = "abc`"
Output: ["a","b","c"]

Example 5:

Input: s = "aaaa"
Output: ["aaaa"]

Example 6:

Input: s = "ababa"
Output: ["ababa"]

Example 7:

Input: s = "a"
Output: ["a"]

Constraints:

1 <= s.length <= 10⁵
s contains only lowercase English letters.

Hint:

Notice that it's impossible for any two valid substrings to overlap unless one is inside another.
We can start by finding the starting and ending index for each character.
From these indices, we can form the substrings by expanding each character's range if necessary (if another character exists in the range with smaller/larger starting/ending index).
Sort the valid substrings by length and greedily take those with the smallest length, discarding the ones that overlap those we took.

Solution:

We compute the minimal valid interval for each character, expand it until every character inside the interval has all its occurrences included, then greedily select non-overlapping intervals sorted by earliest ending time. Ties are broken by shorter interval length to minimize total length.

Approach

Store first[c], last[c], and all positions for every lowercase letter.
For each character c, start with the interval [first[c], last[c]].
Expand the interval until stable:
- If any character k appears inside [l, r], merge all occurrences of k into the interval.
- Update l = min(l, first[k]) and r = max(r, last[k]).
Keep only intervals whose left endpoint equals first[c]; other expanded intervals are duplicates generated by their actual leftmost character.
Sort valid intervals by:
- ending index ascending,
- starting index descending when endings are equal, which prefers shorter intervals.
Greedily choose an interval if its start is greater than the end of the last chosen interval.
Return the chosen substrings using substr.

Let's implement this solution in PHP: 1520. Maximum Number of Non-Overlapping Substrings

`php
<?php
/**

@param String $s
@return String[] / function maxNumOfSubstrings(string $s): array { ... ... ... /*
- go to ./solution.php */ }

// Test cases
echo maxNumOfSubstrings("adefaddaccc") . "\n"; // Output: ["e","f","ccc"]
echo maxNumOfSubstrings("abbaccd") . "\n"; // Output: ["d","bb","cc"]
echo maxNumOfSubstrings("abac") . "\n"; // Output: ["b","c"]
echo maxNumOfSubstrings("abc") . "\n"; // Output: ["a","b","c"]
echo maxNumOfSubstrings("aaaa") . "\n"; // Output: ["aaaa"]
echo maxNumOfSubstrings("ababa") . "\n"; // Output: ["ababa"]
echo maxNumOfSubstrings("a") . "\n"; // Output: ["a"]
?>
`

Explanation:

A valid substring containing character c must contain all occurrences of c, so its minimum possible span is [first[c], last[c]].
If that span contains another character k, then validity forces all occurrences of k to be included too. This may expand the interval again.
Repeating this expansion gives the smallest valid substring that can start at first[c].
The check l === first[c] avoids adding the same expanded interval multiple times.
Valid intervals cannot partially overlap; they are either disjoint or nested. Therefore, greedy earliest-finish selection gives the maximum number of non-overlapping substrings.
For equal ending points, choosing the later starting point gives a shorter substring and does not hurt future choices.
lastEnd tracks the end of the last chosen substring, ensuring no overlap.

Complexity Analysis

Let n = strlen(s) and alphabet size Σ = 26.
Preprocessing: O(n).
Expansion for each character: at most O(Σ^3 log n), which is effectively constant since Σ = 26.
Sorting at most 26 intervals: O(Σ log Σ).
Overall time: O(n + Σ^3 log n), practically O(n).
Space: O(n) for storing character positions, plus O(Σ) extra.

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

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

MD ARIFUL HAQUE — Thu, 17 Sep 2026 17:46:29 +0000

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Difficulty: Medium

Topics: Staff, Array, Hash Table, Binary Search, Dynamic Programming, Sliding Window, Biweekly Contest 28

You are given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with a sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

Example 1:

Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

Example 2:

Input: arr = [7,3,4,7], target = 7
Output: 2
Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

Example 3:

Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1
Explanation: We have only one sub-array of sum = 6.

Example 4:

Input: arr = [1,1,1,1], target = 2
Output: 4

Example 5:

Input: arr = [1,2,1,2], target = 3
Output: 4

Example 6:

Input: arr = [2,2,2,2], target = 4
Output: 4

Example 7:

Input: arr = [1,1,1], target = 2
Output: -1

Example 8:

Input: arr = [1,2,3,4,5], target = 5
Output: 3

Example 9:

Input: arr = [1,1,1,1,1], target = 2
Output: 4

Example 10:

Input: arr = [5], target = 5
Output: -1

Constraints:

1 <= arr.length <= 10⁵
1 <= arr[i] <= 1000
1 <= target <= 10⁸

Hint:

Let's create two arrays prefix and suffix where prefix[i] is the minimum length of sub-array ends before i and has sum = k, suffix[i] is the minimum length of sub-array starting at or after i and has sum = k.
The answer we are searching for is min(prefix[i] + suffix[i]) for all values of i from 0 to n-1 where n == arr.length.
If you are still stuck with how to build prefix and suffix, you can store for each index i the length of the sub-array starts at i and has sum = k or infinity otherwise, and you can use it to build both prefix and suffix.

Solution:

We solve the problem by first finding all subarrays whose sum equals target using a sliding window, then using prefix and suffix minimum-length arrays to combine two non-overlapping valid subarrays with the smallest total length.

Approach

Use a sliding window over the positive integer array to find all contiguous subarrays whose sum equals target.
For each valid subarray [left, right], record its length:
- bestEnd[right] = min(bestEnd[right], length)
- bestStart[left] = min(bestStart[left], length)
Build pref[i]: minimum length of a valid subarray ending at or before index i.
Build suff[i]: minimum length of a valid subarray starting at or after index i.
For every split point i, combine:
- one subarray ending at or before i
- one subarray starting at or after i + 1
Return the minimum pref[i] + suff[i + 1].
If no such pair exists, return -1.

Let's implement this solution in PHP: 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

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

// Test cases
echo minSumOfLengths([3,2,2,4,3], 3) .  "\n";           // Output: 2
echo minSumOfLengths([7,3,4,7], 7) .  "\n";             // Output: 2
echo minSumOfLengths([4,3,2,6,2,3,4], 6) .  "\n";       // Output: -1
echo minSumOfLengths([1,1,1,1], 2) .  "\n";             // Output: 4
echo minSumOfLengths([1,2,1,2], 3) .  "\n";             // Output: 4
echo minSumOfLengths([2,2,2,2], 4) .  "\n";             // Output: 4
echo minSumOfLengths([1,1,1], 2) .  "\n";               // Output: -1
echo minSumOfLengths([1,2,3,4,5], 5) .  "\n";           // Output: 3
echo minSumOfLengths([1,1,1,1,1], 2) .  "\n";           // Output: 4
echo minSumOfLengths([5], 5) .  "\n";                   // Output: -1
?>

Explanation

Because all elements are positive, the sliding window sum is monotonic: expanding right increases the sum, and moving left decreases it.
When sum == target, the current window is a valid subarray.
bestEnd[right] stores the shortest valid subarray ending exactly at right.
bestStart[left] stores the shortest valid subarray starting exactly at left.
The prefix array allows us to know the best valid subarray that finishes before or at a given position.
The suffix array allows us to know the best valid subarray that begins after or at a given position.
Checking every i ensures the two chosen subarrays do not overlap.
INF is used as a sentinel when no valid subarray exists.

Complexity Analysis

Time Complexity: O(n)
- Sliding window: O(n)
- Prefix build: O(n)
- Suffix build: O(n)
- Final combination loop: O(n)
Space Complexity: O(n)
- Arrays bestEnd, bestStart, pref, and suff each use 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

1621. Number of Sets of K Non-Overlapping Line Segments

MD ARIFUL HAQUE — Wed, 16 Sep 2026 17:55:40 +0000

1621. Number of Sets of K Non-Overlapping Line Segments

Difficulty: Medium

Topics: Staff, Math, Dynamic Programming, Combinatorics, Prefix Sum, Biweekly Contest 37

Given n points on a 1-D plane, where the iᵗʰ point (from 0 to n-1) is at x = i, find the number of ways we can draw exactly k non-overlapping line segments such that each segment covers two or more points. The endpoints of each segment must have integral coordinates. The k line segments do not have to cover all n points, and they are allowed to share endpoints.

Return the number of ways we can draw k non-overlapping line segments. Since this number can be huge, return it modulo 10⁹ + 7.

Example 1:

Input: n = 4, k = 2
Output: 5
Explanation:
- The two line segments are shown in red and blue.
- The image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.

Example 2:

Input: n = 3, k = 1
Output: 3
Explanation: The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.

Example 3:

Input: n = 30, k = 7
Output: 796297179
Explanation: The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 10⁹ + 7 gives us 796297179.

Example 4:

Input: n = 2, k = 1
Output: 1

Example 5:

Input: n = 3, k = 2
Output: 1

Example 6:

Input: n = 4, k = 1
Output: 6

Example 7:

Input: n = 1000, k = 999
Output: 1

Constraints:

2 <= n <= 1000
1 <= k <= n-1

Hint:

Try to use dynamic programming where the current index and remaining number of line segments to form can describe any intermediate state.
To make the computation of each state in constant time, we could add another flag to the state that indicates whether or not we are in the middle of placing a line (placed start point but no endpoint).

Solution:

We count valid sets of exactly k non-overlapping line segments by reducing the problem to a single binomial coefficient:

C(n + k - 1, 2k) mod 1_000_000_007.

The given PHP solution precomputes factorials and inverse factorials, then evaluates this combination efficiently.

Approach

Represent a valid drawing as a sequence of 2k endpoints: l1 < r1 <= l2 < r2 <= ... <= lk < rk.
Convert the weak inequalities ri <= li+1 into strict inequalities by shifting alternating endpoints.
This transforms the problem into choosing 2k strictly increasing values from n + k - 1 possible positions.
Therefore, the answer is C(n + k - 1, 2k).
Compute the binomial coefficient modulo 10^9 + 7 using factorials and modular inverses.

Let's implement this solution in PHP: 1621. Number of Sets of K Non-Overlapping Line Segments

<?php
/**
 * @param Integer $n
 * @param Integer $k
 * @return Integer
 */
function numberOfSets(int $n, int $k): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param int $base
 * @param int $exp
 * @param int $mod
 * @return int
 */
function modPow(int $base, int $exp, int $mod): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo numberOfSets(4, 2) . "\n";             // Output: 5
echo numberOfSets(3, 1) . "\n";             // Output: 3
echo numberOfSets(30, 7) . "\n";            // Output: 796297179
echo numberOfSets(2, 1) . "\n";             // Output: 1
echo numberOfSets(3, 2) . "\n";             // Output: 1
echo numberOfSets(4, 1) . "\n";             // Output: 6
echo numberOfSets(1000, 999) . "\n";        // Output: 1
?>

Explanation:

Let p1, p2, ..., p2k be the endpoint sequence:
- p1 = l1, p2 = r1, p3 = l2, p4 = r2, etc.
- The constraints become p1 < p2 <= p3 < p4 <= ... <= p2k-1 < p2k.
Define qj = pj + floor((j - 1) / 2).
- Then q1 < q2 < ... < q2k.
- The maximum possible value of q2k is n + k - 2.
Thus, we need to choose 2k distinct values from 0 to n + k - 2, inclusive.
Number of choices: C(n + k - 1, 2k).
The code computes:
- N = n + k - 1
- R = 2 * k
- If R > N, return 0.
- Precompute fact[0..N].
- Compute invFact[N] = modPow(fact[N], MOD - 2, MOD).
- Fill invFact downward.
- Return fact[N] * invFact[R] * invFact[N - R] % MOD.

Complexity Analysis

Time Complexity: O(n + k + log MOD), dominated by factorial precomputation.
Space Complexity: O(n + k) for factorial and inverse factorial arrays.
With n <= 1000, this is easily within limits.

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

2472. Maximum Number of Non-overlapping Palindrome Substrings

MD ARIFUL HAQUE — Tue, 15 Sep 2026 14:07:00 +0000

2472. Maximum Number of Non-overlapping Palindrome Substrings

Difficulty: Hard

Topics: Senior Staff, Two Pointers, String, Dynamic Programming, Greedy, Weekly Contest 319

You are given a string s and a positive integer k.

Select a set of non-overlapping substrings from the string s that satisfy the following conditions:

The length of each substring is at least k.
Each substring is a palindrome.

Return the maximum number of substrings in an optimal selection.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "abaccdbbd", k = 3
Output: 2
Explanation:
- We can select the substrings underlined in s = "abaccdbbd". Both "aba" and "dbbd" are palindromes and have a length of at least k = 3.
- It can be shown that we cannot find a selection with more than two valid substrings.

Example 2:

Input: s = "adbcda", k = 2
Output: 0
Explanation: There is no palindrome substring of length at least 2 in the string.

Example 3:

Input: s = "a", k = 1
Output: 1

Example 4:

Input: s = "aa", k = 2
Output: 1

Example 5:

Input: s = "aaa", k = 2
Output: 1

Example 6:

Input: s = "ababa", k = 3
Output: 1

Example 7:

Input: s = "abccba", k = 3
Output: 1

Example 8:

Input: s = "racecar", k = 3
Output: 1

Example 9:

Input: s = "abcde", k = 1
Output: 5

Example 10:

Input: s = "aabbaa", k = 2
Output: 2

Example 11:

Input: s = "aabbaa", k = 3
Output: 1

Example 12:

Input: s = "abacaba", k = 3
Output: 2

Constraints:

1 <= k <= s.length <= 2000
s consists of lowercase English letters.

Hint:

Try to use dynamic programming to solve the problem.
let dp[i] be the answer for the prefix s[0…i].
The final answer to the problem will be dp[n-1]. How do you compute this dp?

Solution:

We solve the problem by using dynamic programming combined with palindrome precomputation via the expand-around-center technique. We first identify all palindromic substrings of length at least k, recording their start and end positions. Then, using DP where dp[i] represents the maximum number of non-overlapping palindromes in the prefix s[0...i], we iteratively build the optimal solution by either skipping the current character or ending a valid palindrome at the current position.

Approach

Precompute palindromes: Use expand-around-center for both odd and even length centers to find all palindromic substrings with length ≥ k.
Store palindromes by end index: For each ending position i, store a list of valid start positions j such that s[j...i] is a palindrome of length ≥ k.
Dynamic Programming:
- Define dp[i] as the maximum number of non-overlapping valid palindromes in prefix s[0...i-1].
- Base case: dp[0] = 0.
- Transition:
  - Option 1: Skip character at i-1, so dp[i] = dp[i-1].
  - Option 2: For each palindrome ending at index i-1 starting at j, take dp[j] + 1.
- Take the maximum over all options.
Return dp[n] as the final answer.

Let's implement this solution in PHP: 2472. Maximum Number of Non-overlapping Palindrome Substrings

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

/**
 * Expand around center to find all palindromes with length >= k
 *
 * @param string $s
 * @param int $left
 * @param int $right
 * @param int $k
 * @param array $palindromesEndingAt
 * @param int $n
 * @return void
 */
function expandAroundCenter(string $s, int $left, int $right, int $k, array &$palindromesEndingAt, int $n): void
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maxPalindromes("abaccdbbd", 3) . "\n";         // Output: 2
echo maxPalindromes("adbcda", 2) . "\n";            // Output: 0
echo maxPalindromes("a", 1) . "\n";                 // Output: 1
echo maxPalindromes("aa", 2) . "\n";                // Output: 1
echo maxPalindromes("aaa", 2) . "\n";               // Output: 1
echo maxPalindromes("ababa", 3) . "\n";             // Output: 1
echo maxPalindromes("abccba", 3) . "\n";            // Output: 1
echo maxPalindromes("racecar", 3) . "\n";           // Output: 1
echo maxPalindromes("abcde", 1) . "\n";             // Output: 5
echo maxPalindromes("aabbaa", 2) . "\n";            // Output: 2
echo maxPalindromes("aabbaa", 3) . "\n";            // Output: 1
echo maxPalindromes("abacaba", 3) . "\n";           // Output: 2
?>

Explanation:

Why expand-around-center? It efficiently finds all palindromes in O(n²) time by expanding from each possible center (odd and even).
Why DP? Greedy selection of palindromes doesn't always yield the optimal count because choosing a shorter palindrome early might allow more palindromes later. DP explores all valid combinations.
DP state meaning:
- dp[i] = max palindromes in first i characters (s[0...i-1]).
- This makes transitions natural: either we don't use the i-1-th character, or we use a palindrome ending exactly at i-1.
Non-overlapping guarantee: When we end a palindrome at i-1 starting at j, we add 1 to dp[j], which only considers characters before index j. Hence, no overlap.
Time efficiency: Precomputation takes O(n²), DP takes O(n²) in worst case (if many palindromes), but overall feasible for n ≤ 2000.

Complexity Analysis

Time Complexity:
- Expand-around-center: O(n²)
- DP transitions: O(n²) in worst case (each position can have up to O(n) palindromes ending at it).
- Total: O(n²)
Space Complexity:
- palindromesEndingAt: O(n²) in worst case (storing all palindromes).
- dp array: O(n)
- Total: 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

836. Rectangle Overlap

MD ARIFUL HAQUE — Mon, 14 Sep 2026 17:18:57 +0000

836. Rectangle Overlap

Difficulty: Easy

Topics: Mid Level, Math, Geometry, Weekly Contest 85

An axis-aligned rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) is the coordinate of its bottom-left corner, and (x2, y2) is the coordinate of its top-right corner. Its top and bottom edges are parallel to the X-axis, and its left and right edges are parallel to the Y-axis.

Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two axis-aligned rectangles rec1 and rec2, return true if they overlap, otherwise return false.

Example 1:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false

Example 3:

Input: rec1 = [0,0,1,1], rec2 = [2,2,3,3]
Output: false

Example 4:

Input: rec1 = [0,0,1,1], rec2 = [0,0,1,1]
Output: true

Example 5:

Input: rec1 = [0,0,2,2], rec2 = [1,1,1,1]
Output: false

Example 6:

Input: rec1 = [-5,-5,0,0], rec2 = [-3,-3,2,2]
Output: true

Example 7:

Input: rec1 = [0,0,3,3], rec2 = [3,3,5,5]
Output: false

Example 8:

Input: rec1 = [0,0,5,5], rec2 = [1,1,2,2]
Output: true

Example 9:

Input: rec1 = [0,0,1,2], rec2 = [1,1,2,2]
Output: false

Example 10:

Input: rec1 = [-2,-2,-1,-1], rec2 = [-1,-1,0,0]
Output: false

Constraints:

rec1.length == 4
rec2.length == 4
-10⁹ <= rec1[i], rec2[i] <= 10⁹
rec1 and rec2 represent a valid rectangle with a non-zero area.

Solution:

We determine whether two axis-aligned rectangles overlap by checking if their projections onto both the x-axis and y-axis overlap with positive length. If both projections overlap, the rectangles intersect with positive area; otherwise, they do not overlap.

Approach

Check X-axis overlap: Compute the intersection of the horizontal ranges [x1, x2] of both rectangles. The overlap length is positive only when max(rec1[0], rec2[0]) < min(rec1[2], rec2[2]).
Check Y-axis overlap: Compute the intersection of the vertical ranges [y1, y2] of both rectangles. The overlap length is positive only when max(rec1[1], rec2[1]) < min(rec1[3], rec2[3]).
Combine results: Rectangles overlap if and only if both the x-axis and y-axis overlaps are positive. Return true when both conditions hold, otherwise false.
Strict inequality: Use < instead of <= so that rectangles touching only at edges or corners are not considered overlapping (intersection area must be positive).

Let's implement this solution in PHP: 836. Rectangle Overlap

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

// Test cases
echo isRectangleOverlap([0, 0, 2, 2], [1, 1, 3, 3]) ? "true" : "false";             // Output: true
echo isRectangleOverlap([0, 0, 1, 1], [1, 0, 2, 1]) ? "true" : "false";             // Output: false
echo isRectangleOverlap([0, 0, 1, 1], [2, 2, 3, 3]) ? "true" : "false";             // Output: false
echo isRectangleOverlap([0, 0, 1, 1], [0, 0, 1, 1]) ? "true" : "false";             // Output: true
echo isRectangleOverlap([0, 0, 2, 2], [1, 1, 1, 1]) ? "true" : "false";             // Output: false
echo isRectangleOverlap([-5, -5, 0, 0], [-3, -3, 2, 2]) ? "true" : "false";         // Output: true
echo isRectangleOverlap([0, 0, 3, 3], [3, 3, 5, 5]) ? "true" : "false";             // Output: false
echo isRectangleOverlap([0, 0, 5, 5], [1, 1, 2, 2]) ? "true" : "false";             // Output: true
echo isRectangleOverlap([0, 0, 1, 2], [1, 1, 2, 2]) ? "true" : "false";             // Output: false
echo isRectangleOverlap([-2, -2, -1, -1], [-1, -1, 0, 0]) ? "true" : "false";       // Output: false
?>

Explanation:

Each rectangle is defined by its bottom-left (x1, y1) and top-right (x2, y2) corners.
Projecting a rectangle onto the x-axis gives the interval [x1, x2]; projecting onto the y-axis gives [y1, y2].
Two intervals overlap with positive length when the larger of the two lower bounds is strictly less than the smaller of the two upper bounds.
Applying this logic independently to both axes and combining with logical AND gives the correct overlap condition.
This avoids computing the actual intersection area and works in constant time.

Complexity Analysis

Time Complexity: O(1) — only a fixed number of comparisons and arithmetic operations are performed.
Space Complexity: O(1) — no extra data structures 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