Solve array modulo and parentheses tasks

Implement two tasks:

1. Count subarrays by modulo remainder

• Input: integer array nums (length n), integers K (1 ≤ K ≤ 10^

4. and R (0 ≤ R < K).

• Output: the number of subarrays [i..j] such that (sum(nums[i..j]) mod K) == R.
• Requirements: O(n) time and O(K) space; describe the approach, justify correctness, and analyze complexity. Provide an implementation of countSubarraysByRemainder(nums, K, R).

2. Remove the minimum parentheses to balance a string

• Input: string s containing lowercase letters and parentheses '()'.
• Output: any string formed by deleting the minimum number of parentheses so that the result is a valid, balanced parentheses string (characters’ relative order must be preserved).
• Requirements: O(n) time and O(1) extra space beyond the output; describe the algorithm and provide an implementation.

Count Subarrays by Modulo Remainder

Given an integer array nums of length n and integers K (1 ≤ K ≤ 10^4) and R (0 ≤ R < K), return the number of contiguous subarrays nums[i..j] whose element sum is congruent to R modulo K, i.e. (sum(nums[i..j]) mod K) == R.

Approach: walk a running prefix sum reduced modulo K. For a subarray ending at index j with prefix remainder p, it has remainder R exactly when some earlier prefix had remainder (p - R) mod K. Keep a frequency table of prefix remainders seen so far (seeded with remainder 0 occurring once for the empty prefix) and accumulate matches. Use Python's floored modulo so negative numbers map into [0, K), keeping the math consistent. This runs in O(n) time and O(K) space.

Implement countSubarraysByRemainder(nums, K, R).

Constraints

• 1 ≤ K ≤ 10^4
• 0 ≤ R < K
• nums may contain negative integers, zero, and positives
• n (length of nums) can be 0
• Use floored modulo so negatives map into [0, K)

Examples

Example 1

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

Explanation: There are 7 subarrays whose sum is divisible by 5 (remainder 0).

Example 2

Input: ([5], 9, 0)
Output: 0

Explanation: The only subarray [5] has sum 5; 5 mod 9 = 5, not 0, so no subarray matches.

Hints

1. If two prefix sums leave the same remainder mod K, the subarray between them is divisible by K. Generalize this to a target remainder of R.
2. For a prefix remainder p, you want earlier prefixes with remainder (p - R) mod K. Count them with a hash map.
3. Seed the map with remainder 0 having frequency 1 to account for the empty prefix (subarrays starting at index 0).

Remove Minimum Parentheses to Make Valid

Given a string s of lowercase letters and the characters '(' and ')', delete the minimum number of parentheses so that the resulting string is a valid (balanced) parentheses string, preserving the relative order of the remaining characters. Letters are never removed. Return any one valid result of minimum length removed.

Approach: a single forward scan with a counter of currently-unmatched '('. On '(' increment; on ')' either match it (decrement the counter) or, if there is no open paren to match, mark this ')' for deletion. After the scan, the counter equals the number of '(' that were never closed — remove that many '(' by scanning from the right. This deletes exactly the minimum number of parentheses, runs in O(n) time, and uses O(1) extra space beyond the output buffer.

Implement removeMinParentheses(s).

Constraints

• s consists only of lowercase English letters and the characters '(' and ')'
• Letters must never be removed and relative order must be preserved
• s may be empty
• The result must remove the minimum possible number of parentheses
• Any valid minimum-removal result is accepted (the reference uses a deterministic left-to-right rule)

Examples

Example 1

Input: ('lee(t(c)o)de)',)
Output: 'lee(t(c)o)de'

Explanation: The trailing unmatched ')' is the only paren removed; the rest is already balanced.

Example 2

Input: ('a)b(c)d',)
Output: 'ab(c)d'

Explanation: The early ')' has no opener and is deleted; '(c)' stays balanced.

Hints

1. Track the number of currently unmatched '('. A ')' that arrives when this count is 0 can never be matched, so delete it.
2. After one pass, whatever value the open counter holds is the number of '(' that were never closed — those must be removed too.
3. Remove the surplus '(' by scanning from the right so the deletions land on the last unmatched opens; total deletions are provably minimal.