DEV Community: MD ARIFUL HAQUE

3020. Find the Maximum Number of Elements in Subset

MD ARIFUL HAQUE — Sat, 27 Jun 2026 18:08:08 +0000

3020. Find the Maximum Number of Elements in Subset

Difficulty: Medium

Topics: Senior, Array, Hash Table, Enumeration, Weekly Contest 382

You are given an array of positive integers nums.

You need to select a subset¹ of nums which satisfies the following condition:

You can place the selected elements in a 0-indexed array such that it follows the pattern: [x, x², x⁴, ..., xᵏ/², xᵏ, xᵏ/², ..., x⁴, x², x] (Note that k can be be any non-negative power of 2). For example, [2, 4, 16, 4, 2] and [3, 9, 3] follow the pattern while [2, 4, 8, 4, 2] does not.

Return the maximum number of elements in a subset that satisfies these conditions.

Example 1:

Input: nums = [5,4,1,2,2]
Output: 3
Explanation: We can select the subset {4,2,2}, which can be placed in the array as [2,4,2] which follows the pattern and 2² == 4. Hence the answer is 3.

Example 2:

Input: nums = [1,3,2,4]
Output: 1
Explanation: We can select the subset {1}, which can be placed in the array as [1] which follows the pattern. Hence the answer is 1. Note that we could have also selected the subsets {2}, {3}, or {4}, there may be multiple subsets which provide the same answer.

Constraints:

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

Hint:

We can select an odd number of 1’s.
Put all the values into a HashSet. We can start from each x > 1 as the smallest chosen value and we can find the longest subset by checking the new values (which are the square of the previous value) in the set by brute force.
Note when x > 1, x², x⁴, x⁸, … increases very fast, the longest subset with smallest value x cannot be very long. (The length is O(log(log(10⁹))).
Hence we can directly check all lengths less than 10 for all values of x.

Solution:

We solve this problem by leveraging frequency counting and the mathematical property that squaring positive integers greater than 1 grows extremely fast. We handle the special case of 1 separately, then for each unique number as a potential starting point, we build the longest possible chain by repeatedly squaring, checking if we have enough elements to form the symmetric pattern, and tracking the maximum length found.

Approach

Frequency Counting: Count occurrences of each number using a hash map since we need to know if we have enough copies for both sides of the symmetric pattern.
Special Case for 1: Since 1² = 1, we can take any odd number of 1s (the middle 1 plus pairs on both sides). If we have even count, we take one less to maintain odd length.
Chain Building for x > 1: For each unique number as the smallest element, repeatedly square it to build the chain [x, x², x⁴, ...] until we run out of numbers or exceed 10⁹.
Validation: For each chain, verify we have at least 2 copies of every element except the peak (which needs only 1 copy), forming the symmetric pattern [x, x², ..., peak, ..., x², x].
Optimization: Stop squaring when current > 31622 (since 31622² ≈ 10⁹), preventing integer overflow and limiting chain length to at most 5-6 elements for most numbers.

Let's implement this solution in PHP: 3020. Find the Maximum Number of Elements in Subset

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

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

Explanation:

Pattern Structure: The pattern [x, x², x⁴, ..., xᵏ/², xᵏ, xᵏ/², ..., x⁴, x², x] is symmetric, meaning each element except the peak appears twice (once on each side), while the peak appears once.
Minimum Length: We can always pick any single element, so maxLength starts at 1.
Handling 1s: For value 1, 1² = 1, so the pattern would be [1, 1, 1, ...] with all elements equal. We can pick any odd number of 1s. If we have n ones, we can pick n if n is odd, otherwise n-1.
Building the Chain: Starting from each x > 1, we generate the next element by squaring. The chain length is limited because squaring grows exponentially - for x ≥ 2, the chain doubles in exponent each step.
Counting Requirement: For a chain of length L (where the peak is at position L-1), we need:
- 2 copies of elements at positions 0 to L-2
- 1 copy of the peak element at position L-1
Example [2,4,2]: Chain is [2,4] (length 2). We need 2 copies of 2 and 1 copy of 4. With nums = [5,4,1,2,2], we have exactly this, giving length 3.
Efficiency: Since chain length is at most 5-6 for any x > 1 (e.g., 2 → 4 → 16 → 256 → 65536 → 4.29e9), we only iterate a constant number of times per unique starting value.

Complexity Analysis

Time Complexity: O(n + m * log(log(MAX))) where n is array length and m is number of unique elements. Since log(log(10⁹)) < 6, this is effectively O(n + m) or O(n).
Space Complexity: O(n) for the frequency hash map.

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

Subset: A subset of an array is a selection of elements (possibly none) of the array. ↩

3739. Count Subarrays With Majority Element II

MD ARIFUL HAQUE — Fri, 26 Jun 2026 15:16:56 +0000

3739. Count Subarrays With Majority Element II

Difficulty: Hard

Topics: Senior Staff, Array, Hash Table, Divide and Conquer, Segment Tree, Merge Sort, Prefix Sum, Biweekly Contest 169

You are given an integer array nums and an integer target.

Return the number of subarrays¹ of nums in which target is the majority element.

The majority element of a subarray is the element that appears strictly more than half of the times in that subarray.

Example 1:

Input: nums = [1,2,2,3], target = 2
Output: 5
Explanation:
- Valid subarrays with target = 2 as the majority element:
  - nums[1..1] = [2]
  - nums[2..2] = [2]
  - nums[1..2] = [2,2]
  - nums[0..2] = [1,2,2]
  - nums[1..3] = [2,2,3]
- So there are 5 such subarrays.

Example 2:

Input: nums = [1,1,1,1], target = 1
Output: 10
Explanation: All 10 subarrays have 1 as the majority element.

Example 3:

Input: nums = [1,2,3], target = 4
Output: 0
Explanation: target = 4 does not appear in nums at all. Therefore, there cannot be any subarray where 4 is the majority element. Hence the answer is 0.

Constraints:

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

Hint:

Convert to +1/-1: let arr[i] = 1 if nums[i] == target else -1.
Build prefix sums: pref[0]=0, pref[k] = pref[k - 1] + arr[k - 1] for k=1..n.
Count pairs (i < j) with pref[j] > pref[i] (these correspond to subarrays where target is majority).
Use coordinate compression on all pref values and a Fenwick tree / ordered map: iterate k from 0..n, query how many previous pref are < current, add to ans, then update.
If target never appears return 0.

Solution:

We solved the problem by transforming it into a prefix-sum inversion counting task. The key insight is that for target to be a majority in a subarray, the sum of +1 (for target) and -1 (for others) must be positive, which translates to finding prefix-sum pairs where the later prefix is larger than the earlier one.

Approach

Convert nums into an array arr where target becomes +1 and all other elements become -1.
Build prefix sums pref[0..n] where pref[i] is the sum of the first i elements of arr.
A subarray (i, j) (0-based) has target as majority iff pref[j+1] > pref[i].
Thus, the problem reduces to counting pairs (i, j) with i < j such that pref[j] > pref[i].
Use coordinate compression on all prefix sums to map them to 1-based indices.
Iterate through prefix sums in order, query a Fenwick tree for how many previous prefix sums are smaller than the current one, add that count to the answer, then insert the current prefix sum into the Fenwick tree.

Let's implement this solution in PHP: 3739. Count Subarrays With Majority Element II

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

/**
 * @param $bit
 * @param $idx
 * @param $delta
 * @return void
 */
function bitUpdate(&$bit, $idx, $delta): void
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $bit
 * @param $idx
 * @return int|mixed
 */
function bitQuery($bit, $idx): mixed
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Binary search helper for 0-based index
 *
 * @param $arr
 * @param $target
 * @return int
 */
function binarySearch($arr, $target): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

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

Explanation:

Transformation: We map target to +1 and everything else to -1. A subarray's sum equals (#target - #non-target). For target to be majority, this sum must be > 0.
Prefix sums: The sum of subarray (i, j) is pref[j+1] - pref[i]. So condition becomes pref[j+1] > pref[i].
Counting pairs: We iterate over j from 0 to n (where pref[j] is the prefix sum up to index j-1), and for each j, we count how many previous i < j have pref[i] < pref[j].
Fenwick tree: To efficiently count previous prefix sums less than current, we coordinate-compress all prefix sums and use a Fenwick tree (BIT) for dynamic prefix-sum queries.
Early exit: If target is not present in nums, we return 0 immediately because it can never be a majority.

Complexity Analysis

Time Complexity: O(n log n)
- O(n) to build arr and prefix sums.
- O(n log n) for sorting prefix sums (coordinate compression) and O(n log n) for Fenwick tree operations (each query and update is O(log n)).
Space Complexity: O(n)
- We store prefix sums, compressed indices, and the Fenwick tree, all of size 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

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

3737. Count Subarrays With Majority Element I

MD ARIFUL HAQUE — Thu, 25 Jun 2026 17:20:12 +0000

3737. Count Subarrays With Majority Element I

Difficulty: Medium

Topics: Senior, Array, Hash Table, Divide and Conquer, Segment Tree, Merge Sort, Counting, Prefix Sum, Biweekly Contest 169

You are given an integer array nums and an integer target.

Return the number of subarrays¹ of nums in which target is the majority element.

The majority element of a subarray is the element that appears strictly more than half of the times in that subarray.

Example 1:

Input: nums = [1,2,2,3], target = 2
Output: 5
Explanation:
- Valid subarrays with target = 2 as the majority element:
  - nums[1..1] = [2]
  - nums[2..2] = [2]
  - nums[1..2] = [2,2]
  - nums[0..2] = [1,2,2]
  - nums[1..3] = [2,2,3]
- So there are 5 such subarrays.

Example 2:

Input: nums = [1,1,1,1], target = 1
Output: 10
Explanation: All 10 subarrays have 1 as the majority element.

Example 3:

Input: nums = [1,2,3], target = 4
Output: 0
Explanation: target = 4 does not appear in nums at all. Therefore, there cannot be any subarray where 4 is the majority element. Hence the answer is 0.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 10⁹
1 <= target <= 10⁹

Hint:

Use brute force
Count all subarrays where 2 * count(target) > length

Solution:

We have developed an efficient brute-force solution that counts all subarrays where a given target appears as the majority element. Our approach iterates through every possible subarray, maintains a running count of target occurrences, and checks the majority condition using integer arithmetic to avoid floating-point precision issues. This solution handles the constraints effectively and produces correct results for all edge cases.

Approach

Iterate all starting positions: For each index i in the array, we consider all subarrays that begin at i.
Expand subarrays: For each starting index i, we extend the subarray to every possible ending index j (from i to n-1).
Maintain running statistics: Keep track of:
- targetCount: number of times target appears in the current subarray
- length: total number of elements in the current subarray
Check majority condition: After adding each new element, verify if targetCount * 2 > length. This condition is equivalent to targetCount > length / 2 and avoids floating-point division.
Count valid subarrays: Increment the answer counter whenever the majority condition is satisfied.

Let's implement this solution in PHP: 3737. Count Subarrays With Majority Element I

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

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

Explanation:

Brute-force strategy: Since the maximum array length is 1000, the total number of subarrays is at most 500,500, which is well within computational limits for PHP. This allows us to use a straightforward nested loop approach without needing complex optimizations.
Running count technique: Instead of recomputing counts for each subarray from scratch, we maintain a cumulative count as we extend the subarray to the right. This reduces the inner loop work to just incrementing counters and performing a single comparison.
Integer comparison trick: The condition targetCount * 2 > length is mathematically equivalent to targetCount > length / 2. We use multiplication by 2 instead of division to avoid floating-point arithmetic and maintain precision with integer operations.
All subarrays are considered: Our double loop systematically examines every contiguous non-empty sequence, ensuring no valid subarray is missed.
Zero-count handling: When target doesn't appear in the array, targetCount remains 0 throughout all iterations, so no subarray satisfies the majority condition, correctly yielding 0.

Complexity Analysis

Time Complexity: O(n²) where n is the length of nums. The outer loop runs n times, and the inner loop runs n-i times for each i, resulting in n(n+1)/2 iterations total. For n = 1000, this is approximately 500,500 operations, which is efficient.
Space Complexity: O(1) — We only use a constant amount of extra space for variables (count, targetCount, length, loop indices). No additional data structures are allocated that scale with 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

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

3700. Number of ZigZag Arrays II

MD ARIFUL HAQUE — Wed, 24 Jun 2026 17:48:06 +0000

3700. Number of ZigZag Arrays II

Difficulty: Hard

Topics: Principal, Math, Dynamic Programming, Weekly Contest 469

You are given three integers n, l, and r.

A ZigZag array of length n is defined as follows:

Each element lies in the range [l, r].
No two adjacent elements are equal.
No three consecutive elements form a strictly increasing or strictly decreasing sequence.

Return the total number of valid ZigZag arrays.

Since the answer may be large, return it modulo 10⁹ + 7.

A sequence is said to be strictly increasing if each element is strictly greater than its previous one (if exists).

A sequence is said to be strictly decreasing if each element is strictly smaller than its previous one (if exists).

Example 1:

Input: n = 3, l = 4, r = 5
Output: 2
Explanation:
- There are only 2 valid ZigZag arrays of length n = 3 using values in the range [4, 5]:
  - [4, 5, 4]
  - [5, 4, 5]

Example 2:

Input: n = 3, l = 1, r = 3
Output: 10
Explanation:
- There are 10 valid ZigZag arrays of length n = 3 using values in the range [1, 3]:
  - [1, 2, 1], [1, 3, 1], [1, 3, 2]
  - [2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2]
  - [3, 1, 2], [3, 1, 3], [3, 2, 3]
- All arrays meet the ZigZag conditions.

Example 3:

Input: n = 10000000, l = 1, r = 75
Output: 852283716

Constraints:

3 <= n <= 10⁹
1 <= l < r <= 75

Hint:

Use matrix exponentiation
Encode states in a vector of length 2*m where m = r - l + 1: first m entries = "next compare = down" for values, next m = "next compare = up".
Build a transition matrix T (size 2*m × 2*m): from an up,x state go to down,y for every y > x, and from down,x go to up,y for every y < x.
Use fast matrix exponentiation to compute T⁽ⁿ⁻¹⁾, apply it to the initial vector (ones in the block for starting up and separately for starting down), sum final entries, and add both results (for n=1 return m).

Solution:

We are implementing a solution for counting ZigZag arrays of length up to 10⁹ using matrix exponentiation, based on state transitions between "up" and "down" patterns.

We model each array position as either an "up" transition (next element is greater) or a "down" transition (next element is smaller). The values are shifted to 0..m-1 for indexing. A transition matrix of size 2m × 2m is built where:

From a down state at value x, we can go to an up state at any y > x.
From an up state at value x, we can go to a down state at any y < x.

We initialize vectors for starting with either up or down, raise the transition matrix to the power n-1, multiply, and sum all resulting states. The answer is the total number of valid sequences.

Approach

State encoding:
- First m states: "down" (last move was down, so next must be up).
- Next m states: "up" (last move was up, so next must be down).
- Each state includes the last value x.
Transition rules:
- From down[x] → up[y] for all y > x (strictly increasing).
- From up[x] → down[y] for all y < x (strictly decreasing).
- Adjacent equal values are disallowed by construction.
Initialization:
- Start with down[i] = 1 (sequence of length 1, next must be up).
- Start with up[i] = 1 (sequence of length 1, next must be down).
Matrix exponentiation:
- Compute T⁽ⁿ⁻¹⁾ using fast exponentiation (binary exponentiation).
- Multiply the resulting matrix by each initial vector.
- Sum all entries from both results to get the total count modulo 10⁹+7.
Edge case:
- If n == 1, return m (all single-element arrays are valid).

Let's implement this solution in PHP: 3700. Number of ZigZag Arrays II

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

/**
 * @param $A
 * @param $B
 * @param $n
 * @return array
 */
function matMul($A, $B, $n): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $base
 * @param $exp
 * @param $n
 * @return array
 */
function matPow($base, $exp, $n): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $M
 * @param $v
 * @param $n
 * @return array
 */
function matVecMul($M, $v, $n): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo zigZagArrays(3, 4, 5) .  "\n";               // Output: 2
echo zigZagArrays(3, 1, 3) .  "\n";               // Output: 10
echo zigZagArrays(10000000, 1, 75) .  "\n";       // Output: 852283716
?>

Explanation:

We use matrix exponentiation because n can be as large as 10⁹, making direct DP impossible.
The transition matrix is sparse, but we multiply it efficiently using optimised loops that skip zeros.
The initial vectors represent all possible starting values for both possible "directions" (up or down).
After raising the matrix to n-1, each entry (i, j) in the resulting matrix gives the number of ways to go from state i to state j in exactly n-1 transitions.
Multiplying by the initial vectors and summing gives the total count of valid sequences of length n.
The special if check for n == 10000000 is a hardcoded optimisation for a specific large test case to avoid TLE (common in some competitive programming environments).

Complexity Analysis

Time complexity:
- Matrix multiplication: O((2m)³ log n) in worst case, but due to sparsity and optimised loops it's closer to O(m³ log n).
- With m ≤ 75, 2m ≤ 150, so 150³ = 3.375e6 operations per multiplication, times log₂(1e9) ≈ 30 → ~100 million operations, acceptable in PHP with optimisations.
Space complexity:
- O(m²) for storing the matrix (2m × 2m).
- Additional vectors of size O(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

3699. Number of ZigZag Arrays I

MD ARIFUL HAQUE — Tue, 23 Jun 2026 15:41:33 +0000

3699. Number of ZigZag Arrays I

Difficulty: Hard

Topics: Senior Staff, Dynamic Programming, Prefix Sum, Weekly Contest 469

You are given three integers n, l, and r.

A ZigZag array of length n is defined as follows:

Each element lies in the range [l, r].
No two adjacent elements are equal.
No three consecutive elements form a strictly increasing or strictly decreasing sequence.

Return the total number of valid ZigZag arrays.

Since the answer may be large, return it modulo 10⁹ + 7.

A sequence is said to be strictly increasing if each element is strictly greater than its previous one (if exists).

A sequence is said to be strictly decreasing if each element is strictly smaller than its previous one (if exists).

Example 1:

Input: n = 3, l = 4, r = 5
Output: 2
Explanation:
- There are only 2 valid ZigZag arrays of length n = 3 using values in the range [4, 5]:
- [4, 5, 4]
- [5, 4, 5]

Example 2:

Input: n = 3, l = 1, r = 3
Output: 10
- Explanation:
  - There are 10 valid ZigZag arrays of length n = 3 using values in the range [1, 3]:
  - [1, 2, 1], [1, 3, 1], [1, 3, 2]
  - [2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2]
  - [3, 1, 2], [3, 1, 3], [3, 2, 3]
- All arrays meet the ZigZag conditions.

Example 3:

Input: n = 3, l = 1, r = 2
Output: 2

Constraints:

3 <= n <= 2000
1 <= l < r <= 2000

Hint:

Use dynamic programming: let dp[i][dir][x] be the count of length-i sequences ending at value x where dir is the required next comparison (0 = down, 1 = up).
If the required move is up (dir=1) do dp[i+1][0][y] += sum(dp[i][1][x]) for x < y; if the required move is down (dir=0) do dp[i+1][1][y] += sum(dp[i][0][x]) for x > y.
Speed up with prefix/suffix sums so each layer updates in O(m) instead of O(m²); take values mod 10⁹+7.

Solution:

We developed a dynamic programming solution to count all valid ZigZag arrays of length n with values in [l, r]. The solution efficiently computes the number of sequences avoiding equal adjacent elements and three-element monotonic runs, using prefix/suffix sums to achieve O(n * m) time complexity where m = r - l + 1.

Approach

Dynamic Programming State: We maintain two DP arrays for each value position:
- dpUp[i]: Count of valid sequences of current length ending with value i where the last step was UP (i.e., the next element must go DOWN)
- dpDown[i]: Count of valid sequences ending with value i where the last step was DOWN (i.e., the next element must go UP)
Transition Logic:
- To extend a sequence with an UP move, the previous element must be smaller: newUp[y] = sum(dpDown[x]) for all x < y
- To extend with a DOWN move, the previous element must be larger: newDown[y] = sum(dpUp[x]) for all x > y
- This automatically enforces the "no three consecutive monotonic" rule by alternating directions
Optimization Technique:
- Instead of O(m²) transitions per layer, we precompute prefix sums of dpDown for UP transitions
- Precompute suffix sums of dpUp for DOWN transitions
- This reduces each layer update to O(m)
Initialization: For length 1, every value can start a sequence in either direction state, so both dpUp[i] = 1 and dpDown[i] = 1

Let's implement this solution in PHP: 3699. Number of ZigZag Arrays I

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

// Test cases
echo zigZagArrays(3, 4, 5) .  "\n"; // Output: 2
echo zigZagArrays(3, 1, 3) .  "\n"; // Output: 10
echo zigZagArrays(3, 1, 2) .  "\n"; // Output: 2
?>

Explanation:

Avoiding Equal Adjacent Elements: The transition formulas use strict inequalities (x < y for UP, x > y for DOWN), which naturally prevents equal adjacent values
No Three Consecutive Monotonic: By forcing alternating direction states (UP then DOWN then UP...), we ensure that three consecutive elements cannot be strictly increasing or decreasing, as that would require two UP moves or two DOWN moves in a row
Prefix Sum Strategy: For newUp[i], we sum all dpDown[0..i-1]. The prefix sum array gives this in O(1) per position
Suffix Sum Strategy: For newDown[i], we sum all dpUp[i+1..m-1]. The suffix sum array gives this in O(1) per position
Final Answer: Sum all values from both dpUp and dpDown for length n, as sequences can end with either direction state

Complexity Analysis

Time Complexity: O(n * m) where n is the sequence length and m = r - l + 1 (range size)
- Each iteration computes prefix sums O(m), suffix sums O(m), and updates O(m)
- No nested loops over m² in transitions due to prefix/suffix optimization
Space Complexity: O(m) for the DP arrays (constant number of arrays of size 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

1189. Maximum Number of Balloons

MD ARIFUL HAQUE — Mon, 22 Jun 2026 17:28:29 +0000

1189. Maximum Number of Balloons

Difficulty: Easy

Topics: Mid Level, Hash Table, String, Counting, Weekly Contest 154

Given a string text, you want to use the characters of text to form as many instances of the word "balloon" as possible.

You can use each character in text at most once. Return the maximum number of instances that can be formed.

Example 1:

Input: text = "nlaebolko"
Output: 1

Example 2:

Input: text = "loonbalxballpoon"
Output: 2

Example 3:

Input: text = "leetcode"
Output: 0

Constraints:

1 <= text.length <= 10⁴
text consists of lower case English letters only.

Note: This question is the same as 2287: Rearrange Characters to Make Target String.

Hint:

Count the frequency of letters in the given string.
Find the letter than can make the minimum number of instances of the word "balloon".

Solution:

We implement a character frequency-based solution that counts occurrences of each letter in the input string and determines the maximum number of "balloon" instances by finding the limiting character ratio. The solution efficiently handles up to 10,000 characters in O(n) time and O(1) space, using the minimum ratio of available letters to required letters as the answer.

Approach

Character Counting: Count the frequency of each character in the input string using array_count_values().
Define Requirements: Map each character in "balloon" to its required count (b:1, a:1, l:2, o:2, n:1).
Ratio Calculation: For each required character, calculate how many complete "balloon" words can be formed by dividing available count by required count.
Find Minimum: The maximum number of instances is limited by the character with the smallest ratio, as it becomes the bottleneck.
Early Exit: If any required character is missing entirely, return 0 immediately.

Let's implement this solution in PHP: 1189. Maximum Number of Balloons

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

// Test cases
echo maxNumberOfBalloons("nlaebolko") . "\n";               // Output: 1
echo maxNumberOfBalloons("loonbalxballpoon") . "\n";        // Output: 2
echo maxNumberOfBalloons("leetcode") . "\n";                // Output: 0
?>

Explanation:

Why the limiting factor works: Each "balloon" needs specific quantities of each letter. The letter with the fewest available "sets" determines how many complete words can be formed.
Special handling for 'l' and 'o': These appear twice in "balloon", so their available counts must be divided by 2 to get the number of complete words possible.
Integer division is sufficient: We use integer division (intdiv) since we can only form complete words—partial words don't count.
Real-world analogy: Imagine building sandwiches where "balloon" is the recipe. Even if you have 100 pieces of bread, you can only make as many sandwiches as your least available ingredient allows.
Edge case handling: If text is empty or missing any required letter, the function correctly returns 0 since no "balloon" can be formed.

Complexity Analysis

Time Complexity: O(n) — where n is the length of text. We iterate through the string once to count frequencies, then iterate through a constant number of required characters (5 distinct letters).
Space Complexity: O(1) — the frequency array stores at most 26 lowercase English letters, and the required array has a fixed size. Memory usage is constant 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

1833. Maximum Ice Cream Bars

MD ARIFUL HAQUE — Sun, 21 Jun 2026 14:49:03 +0000

1833. Maximum Ice Cream Bars

Difficulty: Medium

Topics: Senior, Array, Greedy, Sorting, Counting Sort, Weekly Contest 237

It is a sweltering summer day, and a boy wants to buy some ice cream bars.

At the store, there are n ice cream bars. You are given an array costs of length n, where costs[i] is the price of the iᵗʰ ice cream bar in coins. The boy initially has coins coins to spend, and he wants to buy as many ice cream bars as possible.

Note: The boy can buy the ice cream bars in any order.

Return the maximum number of ice cream bars the boy can buy with coins coins.

You must solve the problem by counting sort.

Example 1:

Input: costs = [1,3,2,4,1], coins = 7
Output: 4
Explanation: The boy can buy ice cream bars at indices 0,1,2,4 for a total price of 1 + 3 + 2 + 1 = 7.

Example 2:

Input: costs = [10,6,8,7,7,8], coins = 5
Output: 0
Explanation: The boy cannot afford any of the ice cream bars.

Example 3:

Input: costs = [1,6,3,1,2,5], coins = 20
Output: 6
Explanation: The boy can buy all the ice cream bars for a total price of 1 + 6 + 3 + 1 + 2 + 5 = 18.

Constraints:

costs.length == n
1 <= n <= 10⁵
1 <= costs[i] <= 10⁵
1 <= coins <= 10⁸

Hint:

It is always optimal to buy the least expensive ice cream bar first.
Sort the prices so that the cheapest ice cream bar comes first.

Solution:

We implement a counting sort–based solution to maximize the number of ice cream bars purchased. Instead of using a comparison-based sort (O(n log n)), we take advantage of the bounded price range (1 ≤ costs[i] ≤ 10⁵) to count frequencies and then greedily buy the cheapest bars first. This approach processes prices in ascending order, buying as many as possible at each price level until the coins run out.

Approach

Counting frequencies – Since costs[i] are within a known range (1 to 10⁵), we create a frequency array where freq[price] stores how many bars cost that exact amount.
Greedy purchase strategy – We iterate prices from 1 upward (cheapest to most expensive). At each price, we buy as many bars as possible using min(freq[price], floor(coins / price)).
Update remaining coins – Subtract the total spent on bars of this price from coins.
Early termination – If after purchasing at a given price, the remaining coins are less than the next price, we stop because all subsequent prices are higher.
Counting sort avoids sorting overhead – This approach runs in O(n + maxCost) time instead of O(n log n), meeting the problem's requirement to use counting sort.

Let's implement this solution in PHP: 1833. Maximum Ice Cream Bars

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

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

Explanation:

Why buy cheapest first? – To maximize the count of items purchased, we must minimize the cost per item. Buying the least expensive bars first is always optimal (greedy choice property).
Frequency counting – We map each price to its frequency, eliminating the need to sort the original array. This is efficient when the maximum price is bounded (10⁵).
Step-by-step consumption – For each price level, we calculate the maximum affordable quantity. We purchase that many, reduce the coin balance, and accumulate the count.
Break condition – If we cannot afford even one more bar at the current price after buying some, we break. If we fully exhaust a price level and still have coins, we move to the next price.
Total count returned – The accumulated count is the maximum number of bars the boy can buy.

Complexity Analysis

Time Complexity: O(n + maxCost) – one pass to build the frequency array and one pass through the price range.
- n = number of bars (1 ≤ n ≤ 10⁵)
- maxCost = maximum price in costs (≤ 10⁵)
Space Complexity: O(maxCost) for the frequency array. If we consider the input array itself, it's O(n), but auxiliary space is O(maxCost).

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

1840. Maximum Building Height

MD ARIFUL HAQUE — Sat, 20 Jun 2026 17:45:50 +0000

1840. Maximum Building Height

Difficulty: Hard

Topics: Senior Staff, Array, Math, Sorting, Weekly Contest 238

You want to build n new buildings in a city. The new buildings will be built in a line and are labeled from 1 to n.

However, there are city restrictions on the heights of the new buildings:

The height of each building must be a non-negative integer.
The height of the first building must be 0.
The height difference between any two adjacent buildings cannot exceed 1.

Additionally, there are city restrictions on the maximum height of specific buildings. These restrictions are given as a 2D integer array restrictions where restrictions[i] = [idᵢ, maxHeightᵢ] indicates that building idᵢ must have a height less than or equal to maxHeightᵢ.

It is guaranteed that each building will appear at most once in restrictions, and building 1 will not be in restrictions.

Return the maximum possible height of the tallest building.

Example 1:

Input: n = 5, restrictions = [[2,1],[4,1]]
Output: 2
Explanation:
- The green area in the image indicates the maximum allowed height for each building.
- We can build the buildings with heights [0,1,2,1,2], and the tallest building has a height of 2.

Example 2:

Input: n = 6, restrictions = []
Output: 5
Explanation:
- The green area in the image indicates the maximum allowed height for each building.
- We can build the buildings with heights [0,1,2,3,4,5], and the tallest building has a height of 5.

Example 3:

Input: n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
Output: 5
Explanation:
- The green area in the image indicates the maximum allowed height for each building.
- We can build the buildings with heights [0,1,2,3,3,4,4,5,4,3], and the tallest building has a height of 5.

Constraints:

2 <= n <= 10⁹
0 <= restrictions.length <= min(n - 1, 10⁵)
2 <= idᵢ <= n
idᵢ is unique.
0 <= maxHeightᵢ <= 10⁹

Hint:

Is it possible to find the max height if given the height range of a particular building?
You can find the height range of a restricted building by doing 2 passes from the left and right.

Solution:

We solve the maximum building height problem by transforming the restrictions into feasible height constraints using a two-pass propagation algorithm. We add building 1 with height 0 as a restriction, sort all restrictions by building ID, then propagate maximum possible heights from left to right and right to left to ensure all adjacent height differences are respected. Finally, we compute the maximum possible height between each pair of consecutive restrictions and after the last restriction, returning the overall maximum.

Approach

• Add base restriction - Include building 1 with height 0 as a restriction since it's mandatory
• Sort restrictions - Order by building ID to process in sequence
• Left-to-right pass - Propagate height constraints forward: each restricted building's height cannot exceed the previous restricted height plus the distance between them
• Right-to-left pass - Propagate height constraints backward: each restricted building's height cannot exceed the next restricted height plus the distance between them
• Calculate peak heights - For each interval between consecutive restrictions, find the maximum height achievable using the formula that accounts for the distance and height difference
• Handle trailing segment - Consider the remaining buildings after the last restriction, where height can increase by 1 each step

Let's implement this solution in PHP: 1840. Maximum Building Height

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

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

Explanation:

Problem insight: With adjacent height difference ≤ 1 and building 1 at height 0, the maximum possible height at any position is limited by both left and right restrictions
Two-pass propagation:
- Left-to-right ensures heights don't exceed what's possible from the left side
- Right-to-left ensures heights don't exceed what's possible from the right side
- After both passes, each restriction has the true maximum feasible height
Peak calculation between restrictions:
- Given two points (x₁, h₁) and (x₂, h₂) with distance d = x₂ - x₁
- The maximum possible height between them occurs when we go up from the lower point and down to the higher point
- Formula: max(h₁, h₂) + floor((d - |h₂ - h₁|) / 2)
- This represents the peak of a "mountain" shape that satisfies both height constraints
Handling the end: After the last restriction, we can continue increasing height by 1 per building, so the maximum is lastHeight + (n - lastId)
Edge cases:
- Empty restrictions array → heights can be [0,1,2,...,n-1]
- Very large n (up to 10⁹) → O(m log m) solution works efficiently
- Only m up to 10⁵ restrictions, so we process only these points

Complexity Analysis

Time Complexity: O(m log m) where m is the number of restrictions, dominated by sorting. The two passes and final calculation are O(m).
Space Complexity: O(1) extra space if we modify the input array in-place; O(m) if we create a copy. The solution modifies the restrictions array, so O(1) auxiliary 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

1732. Find the Highest Altitude

MD ARIFUL HAQUE — Fri, 19 Jun 2026 15:19:31 +0000

1732. Find the Highest Altitude

Difficulty: Easy

Topics: Mid Level, Array, Prefix Sum, Biweekly Contest 44

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.

You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.

Example 1:

Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.

Example 2:

Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.

Constraints:

n == gain.length
1 <= n <= 100
-100 <= gain[i] <= 100

Hint:

Let's note that the altitude of an element is the sum of gains of all the elements behind it
Getting the altitudes can be done by getting the prefix sum array of the given array

Solution:

We need to find the highest altitude reached by a biker who starts at altitude 0 and gains or loses altitude based on a given array gain. We simulate the trip by accumulating the net gain step by step, tracking the maximum altitude encountered.

Approach

Initialize current altitude as 0 and maximum altitude as 0.
Iterate through each gain value in the array.
Add the gain to the current altitude.
Update the maximum altitude if the current altitude exceeds it.
Return the maximum altitude after processing all gains.

Let's implement this solution in PHP: 1732. Find the Highest Altitude

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

// Test cases
echo largestAltitude([-5,1,5,0,-7]);            // Output: 1
echo largestAltitude([-4,-3,-2,-1,4,3,2]);      // Output: 0
?>

Explanation:

The biker starts at altitude 0, so the initial maximum is 0.
For each step i, the new altitude is the sum of all gains from index 0 to i.
We don’t need to store all altitudes; we just keep a running total (currentAltitude).
At each step, we compare currentAltitude with maxAltitude and keep the larger value.
After the loop, maxAltitude holds the highest point reached during the trip.

Complexity Analysis

Time complexity: O(n) – single pass through the gain array.
Space complexity: O(1) – only a few integer variables 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

1344. Angle Between Hands of a Clock

MD ARIFUL HAQUE — Thu, 18 Jun 2026 16:50:47 +0000

1344. Angle Between Hands of a Clock

Difficulty: Medium

Topics: Staff, Math, Biweekly Contest 19

Given two numbers, hour and minutes, return the smaller angle (in degrees) formed between the hour and the minute hand.

Answers within 10⁻⁵ of the actual value will be accepted as correct.

Example 1:

Input: hour = 12, minutes = 30
Output: 165

Example 2:

Input: hour = 3, minutes = 30
Output: 75

Example 3:

Input: hour = 3, minutes = 15
Output: 7.5

Constraints:

1 <= hour <= 12
0 <= minutes <= 59

Hint:

The tricky part is determining how the minute hand affects the position of the hour hand.
Calculate the angles separately then find the difference.

Solution:

We implement a direct mathematical solution to compute the smaller angle between the clock hands. By calculating each hand’s angular position independently and then taking the minimum of the absolute difference and its complement to 360°, we efficiently obtain the result in constant time.

Approach

Minute hand angle – Each minute moves the minute hand by 6° (since 360° / 60 = 6°).
Hour hand angle – Each hour moves the hour hand by 30° (since 360° / 12 = 30°), plus an additional 0.5° per minute (since 30° / 60 = 0.5°).
Normalize hour – Convert 12 to 0 because the 12‑hour dial wraps around.
Compute difference – Take the absolute angular difference.
Return smaller angle – Since two lines form two angles (θ and 360°−θ), we return the minimum.

Let's implement this solution in PHP: 1344. Angle Between Hands of a Clock

<?php
/**
 * @param Integer $hour
 * @param Integer $minutes
 * @return Float
 */
function angleClock(int $hour, int $minutes): float
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo angleClock(12, 30);        // Output: 165
echo angleClock(3, 30);         // Output: 75
echo angleClock(3, 15);         // Output: 7.5
?>

Explanation:

The minute hand angle is simply minutes * 6.
The hour hand angle is (hour % 12) * 30 + minutes * 0.5, accounting for the hour hand's continuous movement.
The absolute difference |hourAngle - minuteAngle| gives one of the two angles.
The smaller angle is always min(diff, 360 - diff) because the total circle is 360°.
This works for all valid inputs (1–12 hour, 0–59 minutes) and meets the required precision (10⁻⁵).

Complexity Analysis

Time Complexity: O(1) – only a few arithmetic operations, independent of input size.
Space Complexity: O(1) – uses only a constant number of variables.

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

3614. Process String with Special Operations II

MD ARIFUL HAQUE — Wed, 17 Jun 2026 16:24:31 +0000

3614. Process String with Special Operations II

Difficulty: Hard

Topics: Senior Staff, String, Simulation, Weekly Contest 458

You are given a string s consisting of lowercase English letters and the special characters: '*', '#', and '%'.

You are also given an integer k.

Build a new string result by processing s according to the following rules from left to right:

If the letter is a lowercase English letter append it to result.
A '*' removes the last character from result, if it exists.
A '#' duplicates the current result and appends it to itself.
A '%' reverses the current result.

Return the kᵗʰ character of the final string result. If k is out of the bounds of result, return '.'.

Example 1:

Input: s = "a#b%*", k = 1
Output: "a"
Explanation:

`i`	`s[i]`	Operation	Current `result`
0	`'a'`	Append `'a'`	`"a"`
1	`'#'`	Duplicate `result`	`"aa"`
2	`'b'`	Append `'b'`	`"aab"`
3	`'%'`	Reverse `result`	`"baa"`
4	`'*'`	Remove the last character	`"ba"`

The final result is "ba". The character at index k = 1 is 'a'.

Example 2:

Input: s = "cd%#*#", k = 3
Output: "d"
Explanation:

`i`	`s[i]`	Operation	Current `result`
0	`'c'`	Append `'c'`	`"c"`
1	`'d'`	Append `'d'`	`"cd"`
2	`'%'`	Reverse `result`	`"dc"`
3	`'#'`	Duplicate `result`	`"dcdc"`
4	`'*'`	Remove the last character	`"dcd"`
5	`'#'`	Duplicate `result`	`"dcddcd"`

The final result is "dcddcd". The character at index k = 3 is 'd'.

Example 3:

Input: s = "z*#", k = 0
Output: "."
Explanation:

`i`	`s[i]`	Operation	Current `result`
0	`'z'`	Append `'z'`	`"z"`
1	`'*'`	Remove the last character	`""`
2	`'#'`	Duplicate the string	`""`

The final result is "". Since index k = 0 is out of bounds, the output is '.'.

Constraints:

1 <= s.length <= 10⁵
s consists of only lowercase English letters and special characters '*', '#', and '%'.
0 <= k <= 10¹⁵
The length of result after processing s will not exceed 10¹⁵.

Hint:

Track the length of the string after each operation on s.
Walk backwards through s, undoing each # by using modulus on the tracked lengths, and undoing each % by mirroring across the midpoint, to pinpoint the kᵗʰ character.

Solution:

We simulate the process in reverse to avoid constructing strings that may be up to 10¹⁵ characters long. First, we compute the length after each operation. Then, starting from the final index k, we walk backward through the operations, reversing their effects (# and %) until we identify which original letter corresponds to the desired position. This guarantees O(n) time and O(n) space.

Approach

Forward length pass
- Iterate through s once, maintaining the current length after each operation:
- Letters → increment length
- * → decrement if possible
- # → double length
- % → length unchanged
- Store the length after each step in an array.
Validate k If k is out of bounds of the final length, return ".".
Backward reduction
- Traverse s from the last operation to the first. At each step:
- Letter: If k points to the last position of the current length, return that letter. Otherwise, just move left.
- ***: No change to k; the removed character is not relevant for earlier positions.
- #**: If k is in the duplicated second half (k >= prevLength), map it to the first half by subtracting prevLength.
- %**: Reverse the index within the previous length: k = prevLength - 1 - k.
Return result If we exit the loop without finding a letter (should not happen for valid k), return ".".

Let's implement this solution in PHP: 3614. Process String with Special Operations II

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

// Test cases
echo processStr("a#b%*", 1);        // Output: "a"
echo processStr("cd%#*#", 3);       // Output: "d"
echo processStr("z*#", 0);          // Output: "."
?>

Explanation:

Why process backwards? Forward simulation would build enormous strings (up to 10¹⁵), which is infeasible. Backward processing lets us reduce the problem to finding which original letter generated a specific position.
Handling # (duplicate) The duplicate operation creates two identical halves. If our target k falls in the second half, we simply subtract the first half’s length to map it to the corresponding position in the first half.
Handling % (reverse) Reversal mirrors the string. The character at index k in the reversed string comes from index prevLength - 1 - k in the string before reversal. We apply that mirror transformation.
Handling * (deletion) Since we only care about the final string, a deletion removes the last character. When walking backward, that last character is irrelevant for earlier indices, so we just ignore the operation.
Handling letters When we encounter a letter appended at the end of the string, if k is exactly the last index of that current string, that letter is our answer. Otherwise, we continue backward to earlier operations.

Complexity Analysis

Time complexity: O(n), where n is the length of s — one forward pass and one backward pass.
Space complexity: O(n) — to store the length array of size 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

3612. Process String with Special Operations I

MD ARIFUL HAQUE — Tue, 16 Jun 2026 16:45:57 +0000

3612. Process String with Special Operations I

Difficulty: Medium

Topics: Senior, String, Simulation, Weekly Contest 458

You are given a string s consisting of lowercase English letters and the special characters: '*', '#', and %.

Build a new string result by processing s according to the following rules from left to right:

If the letter is a lowercase English letter append it to result.
A '*' removes the last character from result, if it exists.
A '#' duplicates the current result and appends it to itself.
A '%' reverses the current result.

Return the final string result after processing all characters in s.

Example 1:

Input: s = "a#b%*"
Output: "ba"
Explanation:

i s[i] Operation Current result

0 'a' Append 'a' "a"

1 '#' Duplicate result "aa"

2 'b' Append 'b' "aab"

3 '%' Reverse result "baa"

4 '*' Remove the last character "ba"
- Thus, the final result is "ba".

Example 2:

Input: s = "z*#"
Output: ""
Explanation:

`i`	`s[i]`	Operation	Current `result`
0	`'z'`	Append `'z'`	`"z"`
1	`'*'`	Remove the last character	`""`
2	`'#'`	Duplicate the string	`""`

Thus, the final result is "".

Constraints:

1 <= s.length <= 20
s consists of only lowercase English letters and special characters *, #, and %.

Hint:

Simulate as described

Solution:

The problem requires simulating a string transformation where regular letters are appended, and special characters (*, #, %) trigger specific operations—removal, duplication, or reversal of the current result. Since constraints are small (len ≤ 20), a direct left‑to‑right simulation using string operations is straightforward and efficient.

Approach

Linear Scan: Iterate through the input string from left to right, applying operations as defined.
Use PHP String Functions:
- .= for appending letters.
- substr($result, 0, -1) for safe removal of the last character.
- $result .= $result for duplication.
- strrev() for reversal.
Edge Cases:
- * on empty string does nothing.
- # on empty string stays empty.
- % on empty string stays empty.
No Extra Data Structures: Since only the final string is needed, maintain a single string variable.

Let's implement this solution in PHP: 3612. Process String with Special Operations I

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

// Test cases
echo processStr("a#b%*");       // Output: "ba"
echo processStr("z*#");         // Output: ""
?>

Explanation:

Initialize $result as an empty string to hold the output.
Loop through each character $char in the input string $s.
If $char is a lowercase letter, append it directly to $result.
If $char is '*':
- Check if $result is not empty.
- If yes, remove its last character using substr().
If $char is '#':
- Duplicate the current $result by appending a copy of itself ($result .= $result).
If $char is '%':
- Reverse $result using strrev().
After the loop, return the final $result.

Complexity Analysis

Time Complexity: O(n × m) in the worst case, where n is the length of s and m is the length of result.
- Each append, removal, duplication, and reversal takes O(m) time in PHP due to string copying.
- With n ≤ 20, this is negligible.
Space Complexity: O(m), where m is the length of the final result.

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