An application at Amazon is deployed on n servers connected linearly. The vulnerability of the i-th server is given by vulnerability[i]. The system vulnerability of a contiguous segment of servers is defined as the number of servers in the segment × the maximum vulnerability of the segment. Given the vulnerability array, find the sum of system vulnerabilities of all the segments (subsegments) of the servers. Since the answer can be very large, report it modulo 10⁹ + 7.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ vulnerability[i] ≤ 10⁹

Example

vulnerability = [3, 1, 4]
answer = 34

解法

单调栈。对每个 i 找左侧严格更大、右侧 ≥ 的最近下标，设 l = i - left[i]、r = right[i] - i。v[i] 作为最大值时对所有子段的贡献为 v[i] · l · r · (l + r) / 2。复杂度 O(n)。

def getSystemVulnerability(vulnerability):
    MOD = 10**9 + 7
    INV2 = pow(2, MOD - 2, MOD)
    n = len(vulnerability)

    left = [-1] * n
    stack = []
    for i in range(n):
        while stack and vulnerability[stack[-1]] <= vulnerability[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)

    right = [n] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and vulnerability[stack[-1]] < vulnerability[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)

    ans = 0
    for i in range(n):
        l = i - left[i]
        r = right[i] - i
        contrib = vulnerability[i] * l % MOD * r % MOD * (l + r) % MOD * INV2 % MOD
        ans = (ans + contrib) % MOD
    return ans

import java.util.*;

class Solution {
    public int getSystemVulnerability(List<Integer> vulnerability) {
        final long MOD = 1_000_000_007L;
        final long INV2 = (MOD + 1) / 2;
        int n = vulnerability.size();
        int[] v = new int[n];
        for (int i = 0; i < n; i++) v[i] = vulnerability.get(i);

        int[] left = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && v[stack.peek()] <= v[i]) stack.pop();
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        int[] right = new int[n];
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && v[stack.peek()] < v[i]) stack.pop();
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            long l = i - left[i];
            long r = right[i] - i;
            long contrib = v[i] % MOD * l % MOD * r % MOD * ((l + r) % MOD) % MOD * INV2 % MOD;
            ans = (ans + contrib) % MOD;
        }
        return (int) ans;
    }
}

#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    int getSystemVulnerability(vector<int>& vulnerability) {
        const long long MOD = 1'000'000'007LL;
        const long long INV2 = (MOD + 1) / 2;
        int n = vulnerability.size();
        vector<int> left(n), right(n);
        stack<int> st;

        for (int i = 0; i < n; i++) {
            while (!st.empty() && vulnerability[st.top()] <= vulnerability[i]) st.pop();
            left[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }
        while (!st.empty()) st.pop();

        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && vulnerability[st.top()] < vulnerability[i]) st.pop();
            right[i] = st.empty() ? n : st.top();
            st.push(i);
        }

        long long ans = 0;
        for (int i = 0; i < n; i++) {
            long long l = i - left[i];
            long long r = right[i] - i;
            long long contrib = (long long)vulnerability[i] % MOD * l % MOD * r % MOD * ((l + r) % MOD) % MOD * INV2 % MOD;
            ans = (ans + contrib) % MOD;
        }
        return (int) ans;
    }
};

Amazon Technical Academy (ATA) provides on-demand technical training to current Amazon employees looking to broaden their skill sets. ATA has admitted a group of n prospective trainees with varying skill levels. To better accommodate the trainees, ATA has decided to create classes tailored to the skill levels. A placement examination will return a skill level that will be used to group the trainees into classes, where levels[i] represents the skill level of trainee i. All trainees within a class must have a skill level within maxSpread of one another. Determine the minimum number of classes that must be formed.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ levels[i] ≤ 10⁹ for every i (where 0 ≤ i ≤ n-1)
• 0 ≤ maxSpread ≤ 10⁹

Example

n = 4
levels = [4, 8, 1, 7]
maxSpread = 3
answer = 2

解法

排序后贪心：当前元素超过 start + maxSpread 时开一组新班。复杂度 O(n log n)。

def groupStudents(levels, maxSpread):
    levels.sort()
    classes = 1
    start = levels[0]
    for x in levels:
        if x - start > maxSpread:
            classes += 1
            start = x
    return classes

import java.util.*;

class Solution {
    public int groupStudents(int[] levels, int maxSpread) {
        Arrays.sort(levels);
        int classes = 1;
        int start = levels[0];
        for (int x : levels) {
            if (x - start > maxSpread) {
                classes++;
                start = x;
            }
        }
        return classes;
    }
}

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int groupStudents(vector<int>& levels, int maxSpread) {
        sort(levels.begin(), levels.end());
        int classes = 1;
        int start = levels[0];
        for (int x : levels) {
            if (x - start > maxSpread) {
                classes++;
                start = x;
            }
        }
        return classes;
    }
};

Software developers at Amazon are developing a new library for natural language processing. In one of its modules, every string needs to be preprocessed in a particular manner to find the length of its longest self-sufficient proper substring. A substring is self-sufficient if every character appearing in it appears the same total number of times in the original string. A proper substring is a substring that is not equal to the whole string. Find the length of the longest self-sufficient proper substring of fullString. If no such substring exists, return 0.

Constraints

• 1 ≤ |fullString| ≤ 10⁵
• fullString consists of lowercase English letters

Example

fullString = "abadgdg"
answer = 4

fullString = "aaaaaaa"
answer = 0

解法

贪心划分：自足块是包含其内每个字符所有出现的最小连续区间。求出所有此类块；若 ≥ 2 个，答案为 max(最大块, 总长 - 最小块)。复杂度 O(n)。

def findLongestLength(fullString):
    n = len(fullString)
    last = {c: i for i, c in enumerate(fullString)}

    blocks = []
    l = 0
    r = last[fullString[0]]
    for i in range(n):
        r = max(r, last[fullString[i]])
        if i == r:
            blocks.append(r - l + 1)
            l = r + 1
            if l < n:
                r = last[fullString[l]]

    if len(blocks) < 2:
        return 0
    total = sum(blocks)
    return max(max(blocks), total - min(blocks))

import java.util.*;

class Solution {
    public int findLongestLength(String fullString) {
        int n = fullString.length();
        int[] last = new int[26];
        for (int i = 0; i < n; i++) last[fullString.charAt(i) - 'a'] = i;

        List<Integer> blocks = new ArrayList<>();
        int l = 0, r = last[fullString.charAt(0) - 'a'];
        for (int i = 0; i < n; i++) {
            r = Math.max(r, last[fullString.charAt(i) - 'a']);
            if (i == r) {
                blocks.add(r - l + 1);
                l = r + 1;
                if (l < n) r = last[fullString.charAt(l) - 'a'];
            }
        }

        if (blocks.size() < 2) return 0;
        int total = 0, maxLen = 0, minLen = Integer.MAX_VALUE;
        for (int b : blocks) {
            total += b;
            maxLen = Math.max(maxLen, b);
            minLen = Math.min(minLen, b);
        }
        return Math.max(maxLen, total - minLen);
    }
}

#include <string>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    int findLongestLength(string fullString) {
        int n = fullString.size();
        int last[26] = {0};
        for (int i = 0; i < n; i++) last[fullString[i] - 'a'] = i;

        vector<int> blocks;
        int l = 0, r = last[fullString[0] - 'a'];
        for (int i = 0; i < n; i++) {
            r = max(r, last[fullString[i] - 'a']);
            if (i == r) {
                blocks.push_back(r - l + 1);
                l = r + 1;
                if (l < n) r = last[fullString[l] - 'a'];
            }
        }

        if ((int) blocks.size() < 2) return 0;
        int total = 0, maxLen = 0, minLen = INT_MAX;
        for (int b : blocks) {
            total += b;
            maxLen = max(maxLen, b);
            minLen = min(minLen, b);
        }
        return max(maxLen, total - minLen);
    }
};

In this problem, you are given an integer array arr and you need to perform some operations on the array to make all its elements equal to 0. In one operation, you can select a prefix of the array and either increment all the elements of the prefix by 1 or decrement all the elements of the prefix by 1. Find the minimum number of operations to convert every element of arr to 0.

Constraints

• 1 ≤ n ≤ 10⁵
• −10⁹ ≤ arr[i] ≤ 10⁹

Example

arr = [3, 2, 0, 0, -1]
answer = 5

A team of financial analysts at Amazon has designed a stock indicator to determine the consistency of Amazon's stock in delivering returns daily. The percentage return delivered by the stock each day over the last n days is given as stockPrices (values may be negative). The consistency score is the maximum length of any contiguous subarray stockPrices[l..r] such that every prefix sum within the subarray (i.e. stockPrices[l] + stockPrices[l+1] + … + stockPrices[m] for every l ≤ m ≤ r) is non-negative. Return that maximum length.

Constraints

• 1 ≤ n ≤ 10⁵
• −10⁹ ≤ stockPrices[i] ≤ 10⁹

Example

stockPrices = [1, 1, 2, 3, 1]
k = 0
answer = 5

Amazon Games has launched a two-player game with an array of positive integer points. Each turn, a player picks any integer, adds it to their score, and removes it. Players 1 and 2 alternate with player 1 first. The game ends when the array is empty. Both want to maximize their own score. Find the absolute difference of the two players' scores when both play optimally.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ points[i] ≤ 10⁹

Example

points = [4, 1, 2, 3]
answer = 2

Amazon Games launched a 3-round tournament. Each player has exactly three power boosters. In each round a player picks one booster; higher booster wins the round. Player X "defeats" player Y if some rearrangement of X's three boosters beats Y in at least 2 rounds (against any rearrangement of Y). Count players who can defeat every other player.

Constraints

• 2 ≤ n ≤ 10⁵
• 1 ≤ booster_a[i], booster_b[i], booster_c[i] ≤ 10⁹

Example

n = 4
booster_a = [3, 4, 1, 16]
booster_b = [2, 11, 5, 6]
booster_c = [8, 7, 9, 10]
answer = 2

Amazon's analytics team tracks how data on the n-th item depends on other days. The data on item n is said to depend on day x if there exists some positive integer k such that floor(n / k) = x (where 0 ≤ x ≤ n). Given n, find the sum of all distinct values of x for which such a k exists.

Constraints

• 1 ≤ n ≤ 10¹⁰

Example

n = 5
answer = 8

You are given an integer array arr of size n. Exactly n − 2 of the elements are "normal" numbers. One of the remaining two elements equals the sum of those n − 2 normal numbers, and the other element is the outlier. (The sum element and the outlier element have distinct indices in arr, but may share the same numeric value.) Return the largest possible outlier value across all valid choices of which n − 2 elements are the normal ones.

Constraints

• 3 ≤ n ≤ 10⁵
• 1 ≤ arr[i] ≤ 10⁹

Example

n = 4
arr = [4, 1, 2, 10]
answer = 4

Amazon uses a Pascal-triangle style encryption on numeric tokens. Given an array numbers of single digits (each in 0..9), repeatedly replace the array with a new array of length len(arr) − 1 in which the i-th entry equals (arr[i] + arr[i+1]) mod 10. Continue until exactly 2 digits remain. Return the final encrypted value as a 2-character string (left-padded so the output always has length 2).

Constraints

• 2 ≤ n ≤ 10⁵
• 0 ≤ numbers[i] ≤ 9

Example

numbers = [4, 5, 6, 7]
answer = "04"

Amazon developers are building a regex generator. The regex consists of uppercase English letters, [, and ]. A bracketed group contains distinct uppercase letters and matches any single character in the group. Given strings x, y, z of length n, find the longest lexicographically smallest regex that matches both x and y but does not match z. Return -1 if impossible.

Constraints

• 1 ≤ n ≤ 10⁶
• x, y, z consist of uppercase English letters only.

Example

x = "AB", y = "BD", z = "CD"
answer = "[ABDEFGHIJKLMNOPQRSTUVWXYZ][ABCDEFGHIJKLMNOPQRSTUVWXYZ]"

There are n points; the i-th has weight weight[i] and starts at position i on the x-axis. In one operation, the i-th point moves right by dist[i]. Find the minimum total number of operations to sort the points by weight.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ weight[i], dist[i] ≤ 10⁹

Example

n = 4
weight = [3, 6, 5, 1]
dist = [4, 3, 2, 1]
answer = 5

Amazon Web Services has n servers with capacities. A contiguous segment [l, r] (with r - l + 1 >= 3) is balanced iff capacity[l] == capacity[r] == sum(capacity[l+1..r-1]). Count balanced subsegments.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ capacity[i] ≤ 10⁹

Example

capacity = [9, 3, 3, 3, 9]
answer = 2

For each pair (newPasswords[i], oldPasswords[i]), return "YES" if there is a way to "cycle-shift" some characters of newPasswords[i] (each chosen char c → c+1, with z → a) so that oldPasswords[i] becomes a subsequence; else "NO".

Constraints

• 1 ≤ n ≤ 10
• Sum of all password lengths ≤ 2·10⁵
• |oldPasswords[i]| ≤ |newPasswords[i]|

Example

newPasswords = ["baacbab", "accdb", "baacba"]
oldPasswords = ["abdbc", "ach", "abb"]
answer = ["YES", "NO", "YES"]

Amazon has n items with values items[0..n-1] and m orders. The i-th order is the contiguous range [start[i], end[i]], and contributes every items[j] for start[i] ≤ j ≤ end[i] (with multiplicity) to a global multiset (so an item that lies in k orders is counted k times). For each value query[i], return the number of elements in the multiset that are strictly less than query[i]. Return the answers as an array.

Constraints

• 1 ≤ n, m, q ≤ 10⁵
• 1 ≤ items[i], query[i] ≤ 10⁹
• 0 ≤ start[i] ≤ end[i] < n

Example

n = 5, items = [1, 2, 5, 4, 5], m = 3
start = [0, 0, 1], end = [1, 2, 2]
query = [2, 4]
answer = [2, 5]

You are given an array cost of n item costs. You must choose a single target total T and then build packages, each containing at most 2 items, such that every built package has total cost exactly T. Each item is used in at most one package and an item with cost[i] = T may form a one-item package on its own. Return the maximum number of packages that can be built (over the best choice of T).

Constraints

• 1 ≤ n ≤ 2·10⁵
• 1 ≤ cost[i] ≤ 2000

Example

n = 9
cost = [4, 5, 10, 3, 1, 2, 2, 2, 3]
answer = 4

Amazon must distribute n games (with sizes gameSize[0..n-1]) to k children using identical pen drives of capacity C. Each child receives at least 1 and at most 2 games, every game is given to exactly one child, and the total size of games for any child must not exceed C. Return the minimum capacity C that makes a valid distribution possible.

Constraints

• 1 ≤ k ≤ n ≤ 2·10⁵, n ≤ 2k
• 1 ≤ gameSize[i] ≤ 10⁹

Example

n = 4, gameSize = [9, 2, 4, 6], k = 3
answer = 9

Amazon's monitoring service is comparing n processes. The i-th process has computational load process[i]. Two processes i and j are considered computationally equivalent if |process[i] - process[j]| ≤ m. Given the array process and the threshold m, return the number of unordered pairs (i, j) (with i ≠ j) of computationally equivalent processes.

Constraints

• 1 ≤ n ≤ 2·10⁵
• 1 ≤ process[i] ≤ 10⁸
• 0 ≤ m ≤ 10⁸

Example

n = 4, process = [7, 10, 13, 11], m = 3
answer = 4

Amazon has n servers; the i-th server has health health[i] and belongs to type serverType[i]. You may choose at most m distinct server types; once a type is chosen, all servers of that type are selected. The total health is the sum of health[i] over every selected server. Return the maximum possible total health.

Constraints

• 1 ≤ m ≤ n ≤ 10⁵
• 1 ≤ health[i] ≤ 10⁹
• 1 ≤ serverType[i] ≤ n

Example

n = 4, health = [4, 5, 5, 6], serverType = [1, 2, 1, 2], m = 1
answer = 11

There are n host servers; the throughput of the i-th host is host_throughput[i]. Partition some subset of the servers into disjoint triples (each triple uses 3 distinct servers; any number of servers may be left unused). Each triple contributes the median of its three throughputs to the total. Return the maximum achievable sum of medians.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ host_throughput[i] ≤ 10⁹

Example

n = 5, host_throughput = [2, 3, 4, 5, 4]
answer = 4

Given strings userID1 (length n), userID2 (length m), and a positive integer p, the p-matching score is the number of starting indices i (with 0 ≤ i and i + (m − 1)·p < n) such that the m characters userID1[i], userID1[i+p], userID1[i+2p], …, userID1[i+(m−1)·p] form a permutation of userID2. Return the p-matching score.

Constraints

• 1 ≤ m ≤ n ≤ 10⁶
• 1 ≤ p ≤ 10⁶

Example

userID1 = "acaccaa", userID2 = "aac", p = 2
answer = 2

Amazon has n delivery centers; the i-th currently holds parcels[i] parcels. Each day you must pick a positive integer d and ship exactly d parcels from every center that still has at least d parcels (centers with fewer than d parcels are skipped that day). The day fails (does not count) if no center can ship. Return the minimum number of days needed until every center is empty.

Constraints

• 1 ≤ n ≤ 10⁶
• 0 ≤ parcels[i] ≤ 10⁹

Example

parcels = [2, 3, 4, 3, 3]
answer = 3

You are given a battery cell array charge[0..n−1] (values may be negative). You must repeatedly perform the following operation until only one cell remains: pick any index i and merge charge[i] with one of its current neighbours by adding the chosen neighbour's value into charge[i] and removing the neighbour from the array. You may also discard any cell entirely (without merging) at any time. Equivalently, you must choose a contiguous subarray of the original charge and return its sum; return the maximum achievable single-cell value.

Constraints

• 1 ≤ n ≤ 2·10⁵
• -10⁹ ≤ charge[i] ≤ 10⁹

Example

n = 5, charge = [-2, 4, 3, -2, 1]
answer = 9

You are given an n × n matrix data and an array factor[0..n−1], where factor[i] is the maximum number of elements you may pick from row i. Choose exactly x elements in total (across all rows) so that row i contributes at most factor[i] elements. Return the maximum possible sum of the chosen elements, or -1 if it is impossible to pick x elements under the row constraints.

Constraints

• 1 ≤ n ≤ 1000
• 1 ≤ data[i][j] ≤ 10⁹
• 0 ≤ factor[i] ≤ n
• 0 ≤ x ≤ n²

Example

n = 3, data = [[6, 8, 3], [5, 10, 6], [1, 1, 5]], factor = [2, 1, 3], x = 5
answer = 30

There are n delivery agents; agent i already carries parcels[i] parcels. You must distribute exactly extra_parcels additional parcels (each one assigned to any agent of your choice; parcels are indivisible). Return the minimum possible value of the maximum load over all agents after distribution.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ extra_parcels ≤ 10¹⁵
• 1 ≤ parcels[i] ≤ 10⁹

Example

n = 5, parcels = [7, 5, 1, 9, 1], extra_parcels = 25
answer = 10

Given an n x m grid of '0' / '1' pixels, the greyness of cell (i,j) = (# 1s in row i + # 1s in column j) - (# 0s in row i + # 0s in column j). Find the maximum greyness.

Constraints

• 1 ≤ n, m ≤ 1000

Example

pixels = ["101", "001", "110"]
answer = 2

Player passes n rounds, losing power[i] health each. Health must stay strictly positive. May use armor once on any round to reduce damage to min(armor, power[i]). Find the minimum starting health.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ armor ≤ 10⁹
• 1 ≤ power[i] ≤ 10⁹

Example

power = [1, 2, 6, 7], armor = 5
answer = 12

You are given an array data of length n. Find a permutation p[1..n] of [1..n] such that the sum Σᵢ i · data[p[i] − 1] (for i = 1..n) is maximized. Among all permutations that attain the maximum, return the lexicographically smallest one.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ data[i] ≤ 10⁹

Example

n = 3, data = [2, 1, 2]
answer = [2, 1, 3]

Warehouses 1..n with non-decreasing warehouseCapacity. Each warehouse connects to the nearest hub at position ≥ its own. The hub at position n is fixed; for each query (hubA, hubB), place additional hubs at positions hubA and hubB. Cost of warehouse i connecting to hub at j is warehouseCapacity[j] - warehouseCapacity[i]. Sum the minimum total cost.

Constraints

• 1 ≤ n, q ≤ 2·10⁵
• 1 ≤ warehouseCapacity[i] ≤ 10⁹
• 1 ≤ hubA < hubB < n

Example

warehouseCapacity = [1, 2, 4, 6, 9]
additionalHubs = [[1, 3]]
answer = [13]

Given a string productTypes of lowercase letters and integer m, count the number of split points such that the set of distinct chars shared by the prefix and the suffix has size > m.

Constraints

• 1 ≤ |productTypes| ≤ 10⁵
• 0 ≤ m ≤ 26

Example

productTypes = "abbcac", m = 1
answer = 2

Initially items[] is in the cart. Process query[]: if positive, append to cart; if negative, remove the first occurrence of |x|. Return the final cart.

Constraints

• 1 ≤ n, q ≤ 2·10⁵
• 1 ≤ items[i] ≤ 10⁹
• -10⁹ ≤ query[i] ≤ 10⁹, query[i] != 0

Example

items = [1, 2, 1, 2, 1], query = [-1, -1, 3, 4, -3]
answer = [2, 2, 1, 4]

Given dominos with sizes domino[] (length n), a removal sequence remove[] (permutation of [0..n-1]), and integer min_order, find the maximum number of removals k such that the longest strictly increasing subsequence over the remaining dominos is still ≥ min_order.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ domino[i] ≤ 10⁹
• 0 ≤ remove[i] ≤ n - 1
• 1 ≤ min_order ≤ n

Example

n = 6, domino = [1, 4, 4, 2, 5, 3], remove = [2, 1, 4, 0, 5, 3], min_order = 3
answer = 3

There are total_servers servers arranged in a ring (server 1 is adjacent to server total_servers). A subset of n of them, listed in servers[], must all be visited. You may start at any server in servers, and moving to an adjacent server in the ring takes 1 unit of time. Return the minimum total time required to visit every server in servers.

Constraints

• 1 ≤ total_servers ≤ 10⁵
• 1 ≤ n ≤ total_servers
• 1 ≤ servers[i] ≤ total_servers

Example

total_servers = 8
servers = [2, 4, 7]
answer = 5

You are given a string of digits s_id. In one operation you may pick an index i, remove the digit s_id[i], and reinsert the value min(s_id[i] + 1, 9) at any position of the (now shorter) string. You may perform any number of operations. Return the lexicographically smallest string that can be obtained.

Constraints

• 1 ≤ |s_id| ≤ 2·10⁵

Example

s_id = "26547"
answer = "24677"

You are given an array fruits[0..n−1]. In one operation you may pick any two indices i ≠ j such that fruits[i] ≠ fruits[j] and remove both elements from the array. You may perform any number of operations. Return the minimum possible size of the remaining array.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ fruits[i] ≤ 10⁹

Example

n = 5, fruits = [3, 3, 1, 1, 2]
answer = 1

There are n security centers located at integer positions center[0..n−1] on a number line, and n destinations at positions destination[0..n−1]. You must match each center to a distinct destination (a perfect bijection). The total cost of a matching is Σᵢ |center[i] − destination[match(i)]|. Return the minimum total cost over all matchings.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ center[i], destination[i] ≤ 10⁹

Example

n = 3, center = [1, 2, 2], destination = [5, 2, 4]
answer = 6

Given ratings[n] and impactFactor. Apply exactly one of: multiply a contiguous segment by impactFactor, OR divide a contiguous segment by impactFactor (floor for positive, ceil for negative). Maximize the resulting maximum-subarray sum.

Constraints

• 1 ≤ n ≤ 10⁵
• |ratings[i]| ≤ 10⁹

Example

n = 5, ratings = [5, -3, -3, 2, 4], impactFactor = 3
answer = 12

password and reference strings. For each character c, you may remove an occurrence of c from password at cost cost[c - 'a']. Goal: remove all occurrences of any character in reference. Return the minimum cost.

Constraints

• 1 ≤ |password|, |reference| ≤ 10⁵
• 1 ≤ cost[i] ≤ 100

Example

password = "kkkk"
reference = "k"
cost = [1,1,1,1,1,1,1,1,1,1,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]  # cost['k' - 'a'] = cost[10] = 5
answer = 20

Given size[n] and cost[n]. Increasing size[i] by 1 costs cost[i]. Make all sizes distinct with minimum total cost.

Constraints

• 1 ≤ n ≤ 2·10⁵
• 1 ≤ size[i] ≤ 10⁹
• 1 ≤ cost[i] ≤ 10⁴

Example

n = 4, size = [2, 3, 3, 2], cost = [2, 4, 5, 1]
answer = 7

n piles with boxes[i] boxes; each op moves one box from any nonempty pile to any other. Find the minimum number of operations to reach the minimum possible max-min difference.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ boxes[i] ≤ 10⁹

Example

n = 4, boxes = [5, 5, 8, 7]
answer = 2

You are given an array memory[0..n−1] representing the memory value of each of n chapters. You may read the chapters in any order. After reading the k-th chapter (in your chosen order), your accumulated memory equals the sum of the memory values of the first k chapters you have read. Your total memory points is the sum of these running totals after every chapter (i.e. Σₖ₌₁..ₙ (running sum after k chapters)). Return the maximum achievable total memory points.

Constraints

• 1 ≤ n ≤ 10⁵
• -10³ ≤ memory[i] ≤ 10³

Example

n = 3, memory = [3, 4, 5]
answer = 26

There are n robots placed at integer coordinates (x[i], y[i]). A robot is called idle if there exists at least one other robot directly to its left (same y, smaller x), directly to its right (same y, larger x), directly above (same x, larger y), and directly below (same x, smaller y). Return the number of idle robots.

Constraints

• 1 ≤ n ≤ 10⁵
• -10⁹ ≤ x[i], y[i] ≤ 10⁹

Example

x = [0, 1, 2, 0, 1, 2, 0, 1, 2]
y = [0, 0, 0, 1, 1, 1, 2, 2, 2]
answer = 1

Given values[n] and k, find both the maximum median and the minimum median over all subsequences of length k.

Constraints

• 1 ≤ n ≤ 10⁵
• 0 ≤ values[i] ≤ 10⁹
• 1 ≤ k ≤ n

Example

n = 3, values = [1, 2, 3], k = 2
answer = [2, 1] (max median, min median)

Given a palindrome of lowercase letters, return the lex-smallest palindrome that is a rearrangement of its characters.

Constraints

• 1 ≤ |letters| ≤ 10⁸
• All lowercase; input is a palindrome.

Example

letters = "yxxy"
answer = "xyyx"

Given n items with locations[i]. Op: either pick two items with different locations and ship both (one op), or pick one item and ship it (one op). Find minimum number of ops to ship all.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ locations[i] ≤ 10⁹

Example

n = 5, locations = [1, 8, 6, 7, 7]
answer = 3

You are given a string command of length n over lowercase letters, an array profit[0..n−1], and an integer k. You may execute any subset of the indexed commands (skipping the others). The constraint is that within every maximal run of identical letters in command (i.e. each contiguous block of the same character) you may execute at most k of those commands. Your total profit equals the sum of profit[i] over executed indices. Return the maximum achievable profit.

Constraints

• 1 ≤ n ≤ 2·10⁵
• 1 ≤ profit[i] ≤ 10⁹
• 1 ≤ k ≤ n

Example

n = 5, command = "abbba", k = 2, profit = [1, 4, 2, 10, 3]
answer = 18

You are given a string productSeq over the alphabet {a, b, c, d, e, f, g}. Count the number of non-empty contiguous substrings t of productSeq such that max_freq(t) ≤ distinct(t), where max_freq(t) is the highest occurrence count of any single character in t and distinct(t) is the number of distinct characters appearing in t.

Constraints

• 1 ≤ |productSeq| ≤ 10⁵
• Letters from {a..g} only.

Example

productSeq = "abaa"
answer = 8

Given cost[n] and k. Partition into exactly k contiguous nonempty parts. Cost of part [l..r] is cost[l] + cost[r]. Return [min total cost, max total cost].

Constraints

• 1 ≤ k ≤ n ≤ 2·10⁵
• 1 ≤ cost[i] ≤ 10⁹

Example

cost = [1, 2, 3, 2, 5], k = 3
answer = [14, 18]

You are given a string genome of lowercase letters and a single lowercase character mutation. At every time step (t = 1, 2, …), every occurrence of mutation that currently has a non-mutation character immediately to its left removes that left neighbour from the string (all such removals happen simultaneously). Return the earliest time t after which no further removals occur (i.e. the total number of time steps it takes for the process to stabilise). Return 0 if no removal ever happens.

Constraints

• 1 ≤ |genome| ≤ 10⁵
• mutation is a lowercase letter.

Example

genome = "tamem", mutation = 'm'
answer = 2

Given machines[n] and k. Remove exactly k consecutive elements to minimize the sum of |machines[i+1] - machines[i]| over the remaining array.

Constraints

• 1 ≤ k < n ≤ 2·10⁵
• 1 ≤ machines[i] ≤ 10⁹

Example

machines = [3, 9, 4, 2, 16], k = 3
answer = 6

There are n servers; server i answers request[i] requests per second and has health health[i]. Every second the system sends a number of requests equal to the sum of request[i] over all servers that are still alive at the start of that second. In the same second the developers also pick exactly one still-alive server and reduce its health by k; a server dies as soon as its health reaches 0 or below. Once every server is dead, exactly 1 final request is sent. Choose the attack order that minimises the total number of requests sent, and return that minimum.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ request[i], health[i] ≤ 5·10³
• 1 ≤ k ≤ 5·10³

Example

n = 2, request = [3, 4], health = [4, 6], k = 3
answer = 21

You are given n closed integer intervals where interval i is [a[i], b[i]], and an integer k. You must add exactly one additional interval [a, b] (you may freely choose a and b as long as b − a ≤ k). After adding it, intervals are merged into connected components by overlap or touching. Return the minimum possible number of connected components that result.

Constraints

• 1 ≤ n ≤ 2·10⁵
• 1 ≤ a[i] ≤ b[i] ≤ 10⁹
• 1 ≤ k ≤ 10⁹

Example

intervals = [(1,5), (2,4), (6,6), (7,14), (16,19)], k = 2
answer = 2

You are given an array productSize[0..n−1]. Reorder its elements into some permutation p[0..n−1]. For each prefix p[0..i] define its variation as max(p[0..i]) − min(p[0..i]). Return the minimum possible value of Σᵢ₌₀ⁿ⁻¹ variation(p[0..i]) over all permutations.

Constraints

• 1 ≤ n ≤ 2000
• 1 ≤ productSize[i] ≤ 10⁹

Example

n = 3, productSize = [3, 1, 2]
answer = 3

You are given an array param[0..n−1]. For each i you must choose a non-negative integer secretKey[i] and compute hash[i] = secretKey[i] mod param[i]. Each hash[i] therefore lies in the range [0, param[i] − 1]. Choose the secretKey array to maximise the number of distinct values present in hash[0..n−1], and return that maximum.

Constraints

• 1 ≤ n ≤ 2·10⁵
• 1 ≤ param[i] ≤ 10⁹

Example

n = 3, param = [1, 2, 4]
answer = 3

Given a palindrome string productLabel. Count indices i such that deleting productLabel[i] still leaves a palindrome.

Constraints

• 2 ≤ |productLabel| ≤ 10⁵
• Lowercase letters only.

Example

productLabel = "zzz"
answer = 3

You are given a binary string s of length n. A non-empty contiguous substring is called special if the number of '0' characters in it equals the square of the number of '1' characters in it (i.e. cnt0 = cnt1²). Count the number of special substrings of s.

Constraints

• 1 ≤ |s| ≤ 10⁵

Example

s = "010001"
answer = 4

Given match[n], find the maximum number of non-intersecting matches. Two matches (i, m[i]) and (j, m[j]) intersect iff i < j and m[i] > m[j], or i > j and m[i] < m[j].

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ match[i] ≤ n

Example

match = [3, 1, 4, 2, 3, 5]
answer = 4

You are given a binary string frames of even length n. You may flip any number of bits, and you must end up with a string that can be partitioned into maximal runs of identical characters where every run has even length. First minimise the number of flips required to reach such a string; among all flip patterns that hit that minimum, return the minimum possible number of maximal runs in the resulting string.

Constraints

• 2 ≤ n ≤ 10⁵, n even.

Example

frames = "11100110"
answer = 2  // flip index 4 → "11110000" has 2 runs

There are n warehouses with inventories inventory[0..n−1]. Warehouses are processed one at a time. For each warehouse, you and a co-worker dispatch in alternating turns: you go first and remove dispatch1 units, then your co-worker removes dispatch2 units, and the cycle repeats until inventory hits 0 or below. Whoever performs the final dispatch (the one that drops the inventory to ≤ 0) earns the credit for that warehouse. Your co-worker may skip their own turn — but in total, across all warehouses, they may skip at most skips turns. Choose how to spend those skips to maximise the number of warehouses for which you earn the credit, and return that maximum.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ inventory[i] ≤ 10⁹
• 1 ≤ dispatch1, dispatch2, skips ≤ 10⁹

Example

inventory = [3, 6, 2], dispatch1 = 2, dispatch2 = 3, skips = 1
answer = 2

Choose the maximum number of servers from powers[n] so that, when arranged in a circle, every adjacent pair (including first-last) differs by ≤ 1.

Constraints

• 1 ≤ n ≤ 2·10⁵
• 0 ≤ powers[i] ≤ 10⁹

Example

powers = [4, 3, 5, 1, 2, 2, 1]
answer = 5

Given a permutation packageSequence[n] of [1..n]. In each pass, scan L→R; if current element equals sortedCount + 1, sort it and increment sortedCount. Find the number of passes to sort all.

Constraints

• 1 ≤ n ≤ 10⁶

Example

n = 5, packageSequence = [5, 3, 4, 1, 2]
answer = 3

A permutation of [0..n-1]. Swap arr[i] and arr[j] only if (arr[i] & arr[j]) == k. Find the maximum non-negative k for which the array can be sorted.

Constraints

• 1 ≤ n ≤ 10⁵
• 0 ≤ arr[i] ≤ n - 1

Example

n = 4, arr = [0, 3, 2, 1]
answer = 1

Given n items with warehouses[i]. Op: ship 2 items from different warehouses (1 op), OR ship 1 item alone (1 op). Find minimum ops to ship all. (Same as Problem 45 — repeated under different naming.)

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ warehouses[i] ≤ 10⁹

Example

n = 5, warehouses = [2, 9, 7, 8, 8]
answer = 3

Given values[n], binary state (length n), and integer m. In each operation, pick an index where state[i] = '1', append values[i] to S, then for every "blocked-then-unblocked" rule, change one specific '0' to '1'. Maximize the lexicographic order of S of length m.

Constraints

• 1 ≤ n, m ≤ 10⁵
• 1 ≤ values[i] ≤ 10⁹

requests = [[customerId, quantity, bidAmount, timestamp], ...], total inventory T. Allocate by descending bid; on tie, round-robin by ascending timestamp. Return IDs of customers who get nothing, sorted ascending.

Constraints

• 1 ≤ n ≤ 10⁴
• 1 ≤ customerId, quantity, bidAmount, timestamp, totalInventory ≤ 10⁸

Example

requests = [[1, 5, 5, 0], [2, 7, 8, 1], [3, 7, 5, 1], [4, 10, 3, 3]]
totalInventory = 18
answer = [4]

Given two strings primary and secondary of lowercase letters. Merge interleaving them (preserving each one's order) to form a single string with minimum number of inversions (positions where a higher letter precedes a lower one).

Constraints

• 1 ≤ |primary|, |secondary| ≤ 1000

Example

primary = "zc", secondary = "qd"
answer = 2

Sort bugs[n] by ascending frequency (ties broken by ascending bug code).

Constraints

• 1 ≤ n ≤ 2·10⁵
• 1 ≤ bugs[i] ≤ 10⁶

Example

n = 5, bugs = [3, 1, 2, 2, 4]
answer = [1, 3, 4, 2, 2]

t scenarios. Each has truckCapacities[n] and packageWeights[m]. Delivering a package reduces that truck's capacity to floor(cap/2). Each delivery uses a truck whose current capacity ≥ package weight. Return 1 if all packages deliverable in this scenario, else 0.

Constraints

• 1 ≤ t ≤ 6
• 1 ≤ n, m ≤ 10⁵
• 1 ≤ truckCapacities[i][j], packageWeights[i][k] ≤ 10⁹

Inventory quality[n]. Op: choose two values x and y; replace every x with y at cost = (number of xs). Goal: all occurrences of each quality value must be contiguous. Minimize total cost.

Constraints

• 1 ≤ n ≤ 2·10⁵
• -10⁹ ≤ quality[i] ≤ 10⁹

Example

n = 7, quality = [7, 7, 5, 7, 3, 5, 3]
answer = 4

m hubs in a ring. Travel time between adjacent hubs is transitionTime[i]. Starting at hub 1, visit requestedHubs[] in order. Minimize total travel.

Constraints

• 1 ≤ n ≤ 2·10⁵
• 1 ≤ m ≤ 5000
• 1 ≤ transitionTime[i] ≤ 10⁶

Example

m = 3, n = 4, transitionTime = [5, 2, 1], requestedHubs = [1, 3, 3, 2]
answer = 4

Given affinity[n] (n even) and m rules; each rule (x, y) says "if either index x or y is chosen for a region in one step, the other must be chosen for the opposite region in the next step." Maximize total affinity assigned to regionA over alternating steps (A first).

Constraints

• 2 ≤ n ≤ 10⁵, n even.
• -10⁹ ≤ affinity[i] ≤ 10⁹
• 1 ≤ m ≤ n/2

planCost[n] and featureCost[m]. X incompatible pairs (planIdx, featureIdx) (1-indexed). Find the maximum planCost[p] + featureCost[f] over valid pairs.

Constraints

• 2 ≤ n, m ≤ 10⁵
• 1 ≤ X ≤ min(2·10⁵, n*m - 1)
• 1 ≤ planCost[i], featureCost[i] ≤ 10⁹

Given prices[n], integers k and d. Each op picks two indices (x, y) and a p ≤ k, then prices[x] += p, prices[y] -= p. Make max - min < d with minimum ops.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ prices[i] ≤ 10⁹
• 1 ≤ k ≤ 10⁹
• 2 ≤ d ≤ 10⁹

Given strValue of lowercase letters. Op: pick any proper substring and sort it. Minimum ops to sort the entire string?

Constraints

• 3 ≤ |strValue| ≤ 10⁵

Example

strValue = "zyxpqa"
answer = 3

Given population[n] and binary string unit of length n. A unit at city i > 1 can be moved one step left to city i - 1 (at most once). Maximize total population covered.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ population[i] ≤ 10⁴

Example

n = 5, population = [10, 5, 8, 9, 6], unit = "01101"
answer = 27

n users with start_time[i]..end_time[i]. Each second a user is active contributes 1 to total usage. Find the earliest second T at which the cumulative usage reaches max_usage.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ max_usage ≤ 10¹⁴
• 1 ≤ start_time[i] ≤ end_time[i] ≤ 10⁹

String pipeline; character failedService. Each second, every occurrence of failedService removes the character immediately before it. Find the time when no further removals happen.

Constraints

• 1 ≤ |pipeline| ≤ 2·10⁵

Example

pipeline = "database", failedService = 'a'
answer = 2

Group n servers by security grade. Each group contains servers of one grade; sizes of any two groups differ by at most 1. Minimize the number of groups.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ security[i] ≤ 10⁶

Shopper visits a shop with n items, cost cost[], money m. Buys items left-to-right; each subsequent purchase of item i costs (k_i)·cost[i] where k_i is the number of times this item has been bought so far + 1. Loop around when reaching the end. Return total items bought.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ m ≤ 10¹⁵
• 1 ≤ cost[i] ≤ 2·10⁵

Given max_products and an array tasks[n]. Each day, tasks[i] modifies inventory; if tasks[i] > 0, deliver; if tasks[i] < 0, dispatch; if tasks[i] == 0, inspect (inventory must be ≥ 0). Each morning the manager can emergency-add any number of products at $1 each. Find minimum total emergency products to keep inspections passing, OR -1 if impossible.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ max_products ≤ 10⁹

Given memory[n] (n even). Split into n/2 primary and n/2 backup such that each primary has a backup with memory[B] <= memory[P]. Maximize sum of memory[P] over all primaries.

Constraints

• 2 ≤ n ≤ 2·10⁵
• 1 ≤ memory[i] ≤ 10⁹

n VM types with stocks vmStock[]. Each of m customers takes from the type with highest current availability; revenue from that customer = min_nonzero(current stocks) + max(current stocks). Compute total revenue after serving all customers.

Constraints

• 1 ≤ n ≤ 10⁶
• 1 ≤ vmStock[i] ≤ 10⁶
• 1 ≤ m ≤ 10⁶

Given cost[m]. Op: pick (x, y) where cost[x] % cost[y] == 0 and set cost[x] = cost[y]. Minimize total cost.

Constraints

• 1 ≤ m ≤ 2·10⁶
• 1 ≤ cost[i] ≤ 2·10⁸

Example

m = 5, cost = [3, 6, 2, 6, 25]
answer = 17

Grid expansion: start (p1, q1), end (p2, q2). Each step: add a row (vertical, top) or add a column (horizontal, right). Each added "frontier" gets exactly one filled cell. Count distinct final fillings, mod 998244353.

Constraints

• 1 ≤ p1 ≤ p2 ≤ 1000
• 1 ≤ q1 ≤ q2 ≤ 1000

Example

p1 = 1, q1 = 1, p2 = 2, q2 = 2
answer = 3

Given customer_rating[n], integers k and m. Each op increases one rating by 1 (max k ops total). Maximize the Bitwise AND of any m-sized subset of the modified array.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ customer_rating[i] ≤ 10⁹
• 1 ≤ k ≤ 10⁹
• 1 ≤ m ≤ n

Given power[n]. You can add x_l ≥ 0 to each contiguous segment (different x per chosen segment). Make power non-decreasing; minimize total x added.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ power[i] ≤ 10⁹

Example

n = 5, power = [3, 4, 1, 6, 2]
answer = 7

requestLogs[m] = [[skillId, timeStamp], ...]. For each queryTime[i], count skills NOT receiving any request in [queryTime - timeWindow, queryTime].

Constraints

• 1 ≤ numSkills, m, q ≤ 10⁵
• 1 ≤ requestLogs[i][0] ≤ numSkills
• 1 ≤ requestLogs[i][1], queryTimes[i], timeWindow ≤ 10⁵

Single truck of capacity T. List of packages weights[]. Each delivery uses the truck for one package whose weight ≤ current capacity; after delivery T = floor(T / 2). Return total number of packages deliverable using one truck, maximizing it.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ weights[i], T ≤ 10⁹

Amazon Fresh is planning a delivery route. The delivery area is a 2D grid where 1 is an accessible cell, 0 is blocked (no road), and 9 is the order destination. The truck starts at the top-left corner (always accessible) and may move up / down / left / right. Return the minimum number of steps to reach the cell containing 9, or -1 if unreachable.

Constraints

• 1 ≤ rows, columns ≤ 10³
• Cell values are in {0, 1, 9}; area[0][0] is always accessible.

Example:
area = [[1, 0, 0],
 [1, 0, 0],
 [1, 9, 1]]
minDistance(area) = 3

Numbers are encrypted using a Pascal-Triangle-style scheme. Given an initial array numbers[] of digits (each in [0, 9]), repeatedly replace the array with the array of sums of adjacent elements modulo 10 (i.e., keep only the rightmost digit of each sum). Repeat until exactly 2 digits remain. Return the resulting 2-digit string (with leading zero if needed).

Constraints

• 2 ≤ numbers.length ≤ 5 × 10³
• 0 ≤ numbers[i] ≤ 9

Example:
numbers = [4, 5, 6, 7]
[4,5,6,7] -> [9,11,13] -> mod10 -> [9,1,3]
[9,1,3] -> [10,4] -> mod10 -> [0,4]
findNumber([4,5,6,7]) = "04"

Amazon stores binary numbers as strings of '0', '1', and '!', where '!' is an unknown character that can be replaced with either '0' or '1'. After replacement, every subsequence "01" contributes x errors and every subsequence "10" contributes y errors. Return the minimum total errors achievable, modulo 10⁹ + 7.

Constraints

• 1 ≤ |errorString| ≤ 10⁵
• 0 ≤ x, y ≤ 10⁹
• errorString contains only '0', '1', '!'.

Example:
errorString = "!!!!!!!", x = 23, y = 47
getMinErrors(errorString, x, y) = 0
(replace all '!' with '0' or all with '1' -> no "01" or "10" subsequence)

A defective pan balance over-reads one side by a fixed amount wt. A pair of parcels (i, j) is "balanced" iff |weight[i] - weight[j]| == wt. Given weight[n] and wt, count the number of valid pairs. (One parcel cannot appear in two pairs; we count unordered pairs (i, j).) Return the count modulo 10⁹ + 7.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ weight[i], wt ≤ 10⁹

Example:
weight = [4, 5, 5, 4, 2, 5, 3, 2, 3], wt = 1
countBalancedPairs(weight, 1) = 11
(every (4,5), (2,3), (3,2), (5,4) index-pair with |diff|==1)

A student has already answered answered[i] questions in subject i and needs at least needed[i] to pass it. The student can answer q more questions total, distributing them across subjects however they like. Return the maximum number of subjects that can be passed.

Constraints

• 1 ≤ n ≤ 10⁵
• 0 ≤ answered[i], needed[i], q ≤ 10⁹

Example:
answered = [24, 27, 0], needed = [51, 52, 100], q = 100
gap = [27, 25, 100], sort -> [25, 27, 100]
take 25 + 27 = 52 ≤ 100 (pass 2); +100 = 152 > 100 (stop)
findMaximumNum(answered, needed, q) = 2

Given an array stocksProfit[n] and an integer target, count the number of distinct value pairs (a, b) (with a ≤ b) such that some indices i < j give stocksProfit[i] + stocksProfit[j] == target. Pairs are de-duplicated by value, not by index. If a == b, the value must appear at least twice in the array.

Constraints

• 1 ≤ n ≤ 5 × 10⁵
• 0 ≤ stocksProfit[i] ≤ 10⁹
• 0 ≤ target ≤ 5 × 10⁹

Example:
stocksProfit = [6, 6, 3, 9, 3, 5, 1], target = 12
distinct value pairs summing to 12: (3, 9) and (6, 6)
getDistinctPairs(stocksProfit, target) = 2

Given a customer password c and a system-generated password s, count the number of subsequences of c that are lexicographically greater than s. A sequence x is lex greater than y iff either at the first differing position x[i] > y[i], or |x| > |y| and y is a prefix of x. Return the count modulo 10⁹ + 7.

Constraints

• 1 ≤ |c| ≤ 10⁵
• 1 ≤ |s| ≤ 100
• c and s consist of lowercase English letters.

Example:
c = "bab", s = "ab"
subsequences > s: "b", "ba", "bb", "bab", "b" -> 5
countSecurePasswordVariations(c, s) = 5

SDE II Amazon Shopping is running a reward collection event for its customers. There are n customers and the i-th customer has collected initialRewards[i] points so far. One final tournament is to take place where: The champion earns n additional points The second place earns n - 1 points The third place earns n - 2 points … and the last place earns 1 point Given an integer array initialRewards of length n, representing the initial reward points of the customers before the final tournament: Find the number of customers i (1 ≤ i ≤ n) such that, if the i-th customer wins the final tournament, they would have the highest total points. Note - The total points = initialRewards[i] + n (if they win). Other customers also get points in the tournament depending on their ranks (from n - 1 to 1). You must check if the i-th customer, upon winning, ends up with the highest total score, regardless of how others place.

Constraints

• 1 ≤ n ≤ 10⁵
• 0 ≤ initialRewards[i] ≤ 10⁵
• Complete constraints added on 06-18-2025

Example 1

Input:

initialRewards = [1, 3, 4]
n = 3

Output:

2

Explanation: If the 1st participant wins the final showndown, their total scores would be: 1 + 3 = 4, but this is not the highest possible scores in this scenairo. For example, if the 3rd participant with an initial earned points of 4 comes 2nd, then they would achieve a total of: 4 + 2 = 6 scores which is higher than 1st participant scores. If the 2nd participant wins the final showdown, their total points would be: 3 + 3 = 6, and this is the highest total scores in this situation. Even if the 3rd participant with an initial earned points of 4 comes 2nd, then they would achieve a total of: 4 + 2 = 6 scores which is not greater than 2nd participant scores. If the 3rd participant wins the final showdown, their total scores would be: 4 + 3 = 7, and this is the highest total scores, as there are no other participants that can achieve the total score of 7 in this case. Thus, the participants 2 and 3 are the ones such that, if they win the final showdown, they would have the highest total scores. We return 2 as the output

Example 2

Input:

initialRewards = [5, 7, 9, 11]
n = 4

Output:

1

Explanation: Only the 4th participant is the one who, if they secure victory in the final round, would achieve the highest overall score.

Example 3

Input:

initialRewards = [8, 10, 9]
n = 3

Output:

2

Explanation:

If the 2nd customer wins the final tournament, their total points would be 10 + 3 = 13, the highest possible. If the 3rd customer wins, they would get 9 + 3 = 12. Even if the 2nd customer places 2nd with 10 + 2 = 12, they don't exceed the leader. So customers 2 and 3 are the possible winners → answer is 2.

You have servers servers numbered 0..servers-1, all initially free. The i-th request (0-indexed) arrives at time i and lasts requests[i] seconds. When a request arrives, the lowest-indexed free server takes it; if none is free, the server that becomes free first takes it (ties broken by lowest index). Return the array of server ids assigned to each request.

Constraints

(see source image for exact bounds; standard variant of LC 1882)

Example 1

Input:

servers = 5
requests = [3, 1, 0, 2, 1]

Output:

[0, 1, 0, 2, 1]

Explanation:

(see source for details)

SDE II The team at a TomTom International factory has been assigned a critical optimization task aimed at improving the efficiency of packing a set of boxes, each labeled with a unique ID. These boxes are initially arranged in a single row from left to right, where the ID of the i-th box is represented by the string s_id, which consists of digits ranging from 0 to 9, inclusive. To streamline the packing process, the team has been granted the ability to perform a specific operation an arbitrary number of times, including zero times if necessary. The operation is defined as follows: The team can choose any index within the string s_id and remove the digit at that position. After removing the selected digit, the team can insert a new box with an updated ID. The new ID is determined by computing min(s_id[i] + 1, 9), ensuring that the new ID does not exceed 9. Given the initial arrangement of boxes represented by the string s_id, the goal is to determine the lexicographically minimal string that can be achieved by applying the allowed operations optimally. Clarification on Lexicographic Order: A string X is considered lexicographically smaller than another string Y of the same length if and only if, at the first position where X and Y differ, the corresponding digit in X is smaller than the corresponding digit in Y. Objective: Find and return the lexicographically smallest possible string that can be formed by performing the given operation any number of times.

The developers at Amazon want to perform a reliability drill on some servers. There are n servers where the ith server can serve request[i] number of requests and has an initial health of health[i] units. Each second, the developers send the maximum possible number of requests that can be served by all the available servers. With the request, the developers can also send a virus to one of the servers that can decrease the health of a particular server by k units. The developers can choose the server where the virus should be sent. A server goes down when its health is less than or equal to 0. After all the servers are down, the developers must send one more request to conclude the failure of the application. Find the minimum total number of requests that the developers must use to bring all the servers down. Function Description Complete the function minimumRequests in the editor. minimumRequests has the following parameters:

• 1. int[] request: an array of integers representing the number of requests each server can serve
• 2. int[] health: an array of integers representing the initial health of each server
• 3. int k: an integer representing the health decrease caused by the virus Returns int: the minimum total number of requests to bring all the servers down

Constraints

N/A

Example 1

Input:

request = [3, 4]
health = [4, 6]
k = 3

Output:

21

Explanation: The minimum number of requests required is 21. Explanation image was added on 06-13-2025

Amazon Books is a retail store that sells the newly launched novel "The Story of Amazon". The novel is divided into volumes numbered from 1 to n and unfortunately, all the volumes are currently out of stock. The Amazon team announced that starting today, they will bring exactly one volume of "The Story of Amazon" in stock each of the next n days. On the nth day, all volumes will be there. Being an impatient bookworm, each day you will purchase the maximum number of volumes you can such that: You have not purchased the volume before. You already own all its direct prior volumes. Note: For the ith volume of the novel, all the volumes such that j the volume numbers in ascending order if you purchased some volumes on the ith day the single element -1 if you did not purchase any book Function Description Complete the function buyVolumes in the editor below. buyVolumes has the following parameter: int volumes[n]: an array of integers where the ith integer denotes the volume that is in stock on the ith day Returns int[n][n]: a 2d array of integers where the ith array denotes the volumes purchased on the ith day

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ volumes[i] ≤ n
• Elements in volumes are distinct.

Example 1

Input:

volumes = [2, 1, 4, 3]

Output:

[[-1], [1, 2], [-1], [3, 4]]

Explanation: Initially, all volumes are out of stock T~T On the first day, Volume No.2 becomes available. Since you don't own its prequel (Volume 1) yet, you will not purchase it. The answer for the first day is [-1]. On the second day, Volume N0.1 becomes available. Now, you can puchase both vol.1 and vol.2 together. The answer for the second day is [1, 2] On the third day, Volume No.4 becomes available. Since you do not have one of its prequels (Vol.3) yet, you will not buy Vol.4. The answer for the third day is [-1]. On the fourth day, Volume No.3 becomes available. Now, you can purchase both Vol.3 and Vol.4. The answer for the fourth day is [3, 4]. The final answer is [[-1], [1, 2],[-1], [3, 4]].

Example 2

Input:

volumes = [1, 4, 3, 2, 5]

Output:

[[1], [-1], [-1], [2, 3, 4], [5]]

Explanation:

• Day 1, Volume 1 is released. Purchase volume 1. answer[0] = [1]
• Day 2, Volume 4 is released. No volumes are purchased since you do not own all volumes 1 and 3. answer[1] = [-1]
• Day 3, Volume 3 is released. No volumes are purchased since you do not own volume 2. answer[2] = [-1]
• Day 4, Volume 2 is released. Purchase all three volumes. answer[3] = [2, 3, 4]
• Day 5, Volume 5 is released. Purchase volume 5. answer[4] = [5]

Example 3

Input:

volumes = [1, 2, 3]

Output:

[[1], [2], [3]]

Explanation: Day 1, Volume 1 is released. Purchase volume 1. Day 2, Volume 2 is released. Purchase volume 2. Day 3, Volume 3 is released. Purchase volume 3.

Given an array arr of size n and pairs of size m * 2, where each pair represents the starting and ending index of a subarray, we need to calculate the beauty of the array. The process of calculating the beauty involves creating a beautiful array by processing each pair and appending the subarray defined by the pair to the beautiful array. After processing all pairs, we need to return the summation of the count of values exactly lesser than the values at the unused indexes in the original array. Function Description Complete the function calculateBeautyValues in the editor. calculateBeautyValues has the following parameters:

• 1. int arr[n]: an array of integers
• 2. int pairs[m][2]: an array of pairs representing subarray indexes Returns int: the sum of counts of values less than the values at unused indexes

You are given two lists: price[]: A list of integers representing the prices of different stocks. futurePrice[]: A list of integers representing the future prices of those stocks. principle: An integer representing the amount of money you have available to invest. You can buy as many stocks as you want, but the total cost of the stocks you buy must not exceed your principle. Task: Write a function that calculates the maximum profit you can make by buying stocks, where: The profit for each stock is calculated as the difference between its futurePrice and price (i.e., futurePrice[i] - price[i]). You can buy a stock only if its price is less than or equal to the available principle. Constraints

) You can buy any number of stocks, as long as the total price of the selected stocks is less than or equal to principle. If you can't buy any stock (because all stock prices exceed the principle), the maximum profit is 0. The 1010th thank you is being carried by USPS to spike!

Constraints

See above

Example 1

Input:

price = [10, 50, 30, 40, 70]
futurePrice = [100, 40, 50, 30, 90]
principle = 100

Output:

110

Explanation:

Imagine you're a seller on Amazon, specializing in eco-friendly products. Each of your items is rated by customers based on its quality and environmental impact. The overall qualityScore of your products is determined by the maximum possible sum of consecutive ratings. To improve the qualityScore of your products and attract more customers, you are given with an integer impactFactor and the following two strategies: Amplify Ratings: Select a contiguous segment of ratings and amplify them by multiplying each rating in that range by impactFactor. Adjust Ratings: Select a contiguous segment of ratings and adjust them by dividing each rating in that range by impactFactor Your task is to determine the maximum possible qualityScore for your eco-friendly products after applying exactly one of these strategies. Note: When applying the second strategy i.e., Adjust Ratings; For dividing positive ratings, floor the division result, and for dividing negative ratings, use the ceiling value of the division result, Example: Given ratings = [4, -5, 5, -7, 1], and impactFactor = 2. If we choose to apply the second strategy with segment [2, 5] (Assuming 1-based indexing) then, modified ratings: [4, ceil(-5/2), floor(5/2 [I think it should be 5/2 instead of S / 2], ceil(-7/2), floor(1/2)] = [4, -2, 2, -3, 0]. Note that the ceil(-7/2) = -3 and floor(5/2) = 2, Given an array of ratings of size n and an integer impactFactor, determine the maximum possible qualityScore i.e., maximum possible sum of consecutive ratings by optimally selecting exactly one of the strategies to modify the ratings. Function Description Complete the function calculateMaxQualityScore in the editor below calculateMaxQualityScore has the following parameters:

• int impactFactor: the value used in the strategies to amplify or adjust ratings.
• int ratings[n]: an array representing the ratings of eco-friendly products Returns long: the maximum possible qualityScore of your eco-friendly products after applying exactly one of the strategies. Possible solution hint -> Basically, if the array is not entirely negative, find the max sum subarray and multiply it by the factor. If the array is entirely negative, find the single largest negative number and divide it by the factor. Hello spike! Thanks for carrying~

Constraints

• 1 ≤ n ≤ 2 * 10⁵
• 1 ≤ impactFactor ≤ 10⁴
• -10⁵ ≤ ratings[i] ≤ 10⁵

Example 1

Input:

impactFactor = 2
ratings = [5, -3, -3, 2, 4]

Output:

12

Explanation: Let's try both the strategies with different contiguous ranges to get the maximum qualityScore: If we perform the first strategy on the subsegment [4, 5] (1-based indexing), we get the ratings = [5, -3, -3, 4, 8] with a qualityScore of 12, which is the maximum qualityScore. Hence, the answer is 12.

Example 2

Input:

impactFactor = 1
ratings = [-2, 3, -3, -1]

Output:

3

Explanation: Since impactFactor = 1, applying any strategy will not change the ratings. The initial qualityScore is the maximum sum of consecutive ratings, which is 3. Note - The test cases and constraints are slightly different between the two sources I found. Example 1 and constraints are from source 1, while example 2 is from source 2.

You work at a company that has 5 offices, each with a distinct salary level and a priority ranking from lowest to highest as follows: Office A ($1)<OfficeB($10)< Office C ($100)<OfficeD($1,000)< Office E($ 10,000). Your work schedule is represented by a string, where each character corresponds to an office (e.g., 'D' for Office D) you work on the ith day. Your salary is calculated based on the following rule: Salary Calculation Rules: If you work in an office and no higher-priority office appears after it in the sequence, you add its salary to your total salary. If you work in an office and a higher-priority office appears later in the sequence, you subtract its salary from your total salary. The company allows you to change the office you work in, on any one day to maximise your total salary. Your task is to determine the maximum possible salary after making at most one such change. Input Format The first and only line contains a string S representing the sequence offices you worked in. Output Format Print the max salary you can get after changing at most one office to another office.

Example 1

Input:

schedule = "ABCDEEDCBA"

Output:

31000

Explanation: Not found for this time ↔. Lets make a wish to find it in the near future If you happen to know about it you are more than welcome to let us know. Thank you so much for carrying!

You are given a list of packets of varying sizes and there are n channels. Each of the n channel must have a single packet Each packet can only be on a single channel The quality of a channel is described as the median of the packet sizes on that channel. The total quality is defined as sum of the quality of all channels (round to integer in case of float). Given the packet sizes and num of channels, find the maximum quality. Function Description Complete the function calculateMedianSum in the editor. calculateMedianSum has the following parameters:

• int[] packets: an array of integers
• int n: the number of channels Returns int: the sum of the medians of each channel

Constraints

• 1 ≤ n ≤ packets.length ≤ 10⁵
• 1 ≤ packets[i] ≤ 10⁹

Example 1

Input:

packets = [1, 2, 3, 4, 5]
n = 2

Output:

8

Explanation: If packet {1, 2, 3, 4} is sent to channel 1, the median of that channel would be 2.5 If packet {5} is sent to channel 2, its median would be 5 Max total quality is 2.5 + 5 = 7.5 ~ 8

Example 2

Input:

packets = [5, 2, 2, 1, 5, 3]
n = 2

Output:

7

Explanation: channel 1 -> {2, 2, 1, 3,}, median = 2 channel 2 -> {5, 5}, median = 5 total quality 2 + 5 = 7

Giving position of trucks and they are always moving towards end station as it is a gas station. Given a second array indicating extra gas station position in 1-indexing. Calculate the total distance travelled by all the trucks. Example: Given trucks at positions [0,2,5,9,12,18] and extra gas stations at positions [[2,5],[3]], the answer to be returned is [12,18]. The solution can be solved in O(n²) time complexity with one for loop for traversing gas station array and a second loop to calculate total distance travelled. However, there are test cases where this approach may not be optimal. Function Description Complete the function calculateTotalDistanceTravelled in the editor. calculateTotalDistanceTravelled has the following parameters:

• 1. int[] trucks: an array of integers indicating the initial positions of the trucks
• 2. int[][] extraGasStations: a 2D array of integers indicating the positions of extra gas stations Returns int[]: an array of integers indicating the total distance travelled by all the trucks

Trucks dispatch packages in a city. There are n trucks numbered 0, 1, ..., n - 1 used for dispatching goods. Assuming the trucks are parked along the x-coordinate axis, the coordinates of these trucks can be represented as a non-decreasing array called position, where the truck numbered i is parked at position[i]. Each truck can move towards increasing positions of x-coordinates only. At the start of the day, each truck is refuelled. There is a gas station at the position of truck number n - 1, i.e., at position[n - 1], and all other trucks can travel to this position for refuelling. The total distance travelled is the sum of distances travelled by each truck to reach the last x-coordinate position. Thus, the total distance is: (position[n - 1] - position[0]) + (position[n - 1] - position[1]) + ... + (position[n - 1] - position[n - 1]) Two additional gas stations are located at the positions of two trucks, positions a and b. Treat a and b as 1-based indexes into the position array. Given q queries of the form (a, b) where a < b, find the total distance travelled by all the trucks to refuel their tanks. Assume additional gas stations are installed at position[a - 1] and position[b - 1] for each query, and that each truck stops at the nearest gas station going in the forward direction (increasing position). Note that each query is independent, and there is always a gas station at the last position. Function Description Complete the function calculateTruckDistanceAfterRefueling in the editor. calculateTruckDistanceAfterRefueling has the following parameters:

• int[] position: an array of integers representing the positions of trucks
• int[][] extraGasStations: a 2D array of integers where each element extraGasStations[i] contains two integers a and b representing the 1-based indexes of the positions where extra gas stations are installed for the ith query Returns long integer: the total distance travelled by all the trucks after refueling at the nearest gas station for each query

Constraints

:P

Example 1

Input:

position = [3, 6, 10, 15, 20]
extraGasStations = [[2, 4]]

Output:

8

Explanation: There are n = 5 trucks, and their positions are position = [3, 6, 10, 15, 20]. There is q = 1 query with extra gas stations at extraGasStations = [[2, 4]]. Once extra gas stations are installed at position[2 - 1] = 6 and position[4 - 1] = 15:

• 0th truck will move towards x = 6.
• 1st truck will not move since there is already a gas station installed.
• 2nd truck will move towards x = 15. Recall that trucks can move in increasing x-coordinate/position only.
• 3rd truck will not move since there is already a gas station installed.
• 4th truck will not move since there is already a gas station installed. Total distance travelled: (6 - 3) + (6 - 6) + (15 - 10) + (15 - 15) + (20 - 20) = 3 + 0 + 5 + 0 + 0 = 8.

The supply chain manager at one of Amazon's warehouses wants to measure the efficiency of the way parcels are shipped. The volume of each parcel is represented in the array parcelWeights. Each day, the first and last parcels in the array parcelWeights are shipped until all of them are dispatched. The manager comes up with metrics to calculate warehouse efficiency. Each day before shipping, any parcel in the warehouse is chosen and its volume is added to the sum of total efficiency. A parcel can only be chosen once. Given the array parcelWeights, find the maximum possible efficiency of the warehouse.

Constraints

1≤n≤2x10⁵ 0≤parcle_weights[i]≤10⁹

Example 1

Input:

parcelWeights = [4, 4, 8, 5, 3, 2]

Output:

17

Explanation:

Example 2

Input:

parcelWeights = [2,1,8,5,6,2,4]

Output:

23

Explanation: In case 1, the order of picked parcels would produce an answer of 4 + 2 + 8 + 5 = 19, which is incorrect. The correct selection of parcels would be in scenario 2, where the answer will be 4 + 6 + 8 + 5 = 23.

Amazon recently conducted interviews where the candidates were asked to sort the permutation p of length n. Then the ith candidate sorted the permutation in moves[i] moves. To verify the result once more, the interviewer wants to find if it is possible to sort the given permutation in the given number of moves. Given the original permutation array p and the number of moves made by each of the q candidates, find whether you can sort the permutation p by performing exactly moves[i] moves. In one move, you swap the value at any two distinct indexes. Return the answer as a binary string of length q. The value at the ith index should be 1 if it is possible to sort the permutation in exactly moves[i] moves, otherwise the value should be 0. Note: A permutation is a sequence of n distinct integers such that each integer between [1, n] appears exactly once. For example, [1, 2, 3, 4] is a permutation of size 4, but [1, 3, 4, 5] or [1, 2, 2, 4] is not.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ q ≤ 10⁵
• 1 ≤ moves[i] ≤ 10⁹
• It is guaranteed that p forms a permutation.

Example 1

Input:

p = [2, 3, 1, 4]
moves = [2, 3]

Output:

"10"

Explanation: For the first candidate with 2 moves:

• Swap index 0 and 2 (Permutation becomes [1, 3, 2, 4])
• Swap index 1 and 2 (Permutation becomes [1, 2, 3, 4]) The permutation is sorted in exactly 2 moves, so the answer is 1 for the first candidate. For the second candidate with 3 moves, it is not possible to sort the permutation in exactly 3 moves, so the answer is 0 for the second candidate. The final answer is "10".

Example 2

Input:

p = [4, 5, 1, 3, 2]
moves = [1, 2, 3]

Output:

"011"

Explanation: Outputs from these two examples are educated guesses :) It is not possible to sort the permutation in exactly 1 move, so the answer is 0 for the first candidate. For the second candidate with 2 moves:

• Swap index 0 and 4 (Permutation becomes [2, 5, 1, 3, 4])
• Swap index 1 and 2 (Permutation becomes [2, 1, 5, 3, 4]) The permutation is not sorted, so the answer is 0 for the second candidate. For the third candidate with 3 moves, it is possible to sort the permutation, so the answer is 1 for the third candidate. The final answer is "011".

Amazon has recently established n distribution centers in a new location. They want to set up 2 warehouses to serve these distribution centers. Note that the centers and warehouses are all built along a straight line. A distribution center has its demands met by the warehouse that is closest to it. A logistics team wants to choose the location of the warehouses such that the sum of the distances of the distribution centers to their closest warehouses is minimized. Given an array dist_centers, that represent the positions of the distribution centers, return the minimum sum of distances to their closest warehouses if the warehouses are positioned optimally. Function Description Complete the function minSumDistancesToWarehouses in the editor. minSumDistancesToWarehouses has the following parameter:

• int[] dist_centers: an array of integers representing the positions of the distribution centers Returns int: the minimum sum of distances to their closest warehouses

SDE II A prominent media company (AMZ MGM) has partnered with select theaters to showcase exclusive video content, including feature films, episodic series, live performances, and more. You are given an integer n, representing the number of scheduled screenings. Each screening has a start time, duration, and expected audience size, which are provided as integer arrays start, duration, and volume, respectively. Your task is to determine the highest possible total audience size while ensuring that no two selected screenings overlap. Two screenings are considered non-overlapping if one fully concludes before the next one begins. Function Description Complete the function cinemaShows in the editor below. cinemaShows has the following parameter(s):

• int start[n]: an integer array denoting the start times of each show
• int duration[n]: an integer array denoting the durations of each show
• int volume[n]: an integer array denoting the volumes of each show Returns int: an integer denoting the maximum possible volume that can be received

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ start[i] ≤ 10⁹
• 1 ≤ duration[i] ≤ 10⁹
• 1 ≤ volume[i] ≤ 10³

Example 1

Input:

start = [10, 5, 15, 18, 30]
duration = [20, 12, 20, 35, 35]
volume = [50, 51, 20, 25, 10]

Output:

76

Explanation:

Example 2

Input:

start = [1, 2, 4]
duration = [2, 2, 1]
volume = [1, 2, 3]

Output:

4

Explanation: Will udpate once find more reliable resources :) As always

A circular route has n stops numbered from 0 to n - 1. The array distances has length n, where distances[i] is the distance from stop i to stop (i + 1) % n. You are given several route queries. Each query [start, end] asks for the shorter of the two possible distances between those stops on the circle. Return the sum of the shortest distances over all queries.

Constraints

Stops are zero-indexed. Each query contains two valid stop indices. No numeric limits were provided in the source; an efficient solution should precompute prefix sums around the circle.

Example 1

Input:

distances = [1,2,3,4]
queries = [[0,1],[1,3],[3,0]]

Output:

10

Explanation: The shortest distances are 1, 5, and 4, so the total is 10.

Example 2

Input:

distances = [7,10,1,12]
queries = [[0,2],[2,1]]

Output:

23

Explanation: For 0 to 2, the counter-clockwise route is shorter with distance 13. For 2 to 1, the opposite direction has distance 10.

Data Scientists at Amazon are working on cleansing a machine learning dataset. The dataset is represented as a string dataset consisting of an even number of lowercase English letters. The goal is to clean the dataset efficiently by performing specific operations. Here's how the operations work:

• In each operation, two characters from the dataset are selected and removed.
• Each operation has an associated cost:
• x: the cost of removing two identical characters.
• y: the cost of removing two different characters. The task is to determine the optimal strategy that minimizes the total cost to completely clean up the dataset. In other words, find the minimum cost required to remove all characters and make the dataset empty. Function Description Complete the function cleanupDataset in the editor. cleanupDataset has the following parameters:
• String dataset: a string that denotes a machine learning dataset
• int x: the cost of operation when the removed characters are equal
• int y: the cost of operation when the removed characters are unequal Returns int: the minimum cost to clean up the dataset or make the string empty Many Thankssss to da best --> jake !!

Constraints

• 2 ≤ |dataset| ≤ 10⁵
• |dataset| is even
• 1 ≤ x, y ≤ 10⁴

Example 1

Input:

dataset = "aaabca"
x = 3
y = 2

Output:

7

Explanation: In the first operation, the first and second characters are deleted from the dataset, resulting in dataset = "abca". The cost of this operation is x = 3 because both removed characters are equal (also 'a'). In the next operation, the first and third characters are deleted, making dataset = "ba". The cost of this operation is y = 2 because the removed characters are not equal. In the final operation, the remaining two characters are deleted, making the dataset an empty string. The cost of this operation is y = 2 because the removed characters are not equal. Hence, the total cost is 3 + 2 + 2 = 7.

Example 2

Input:

dataset = "ouio"
x = 2
y = 4

Output:

6

Explanation: Operation 1 - Action: removed the first and last characters of the dataset, resulting in the string dataset = "ui". Cost: x = 2 (since both removals, 'o' and 'o' are the same) Operation 2 - Action: delete the remaining characters of "ui", making dataset an empty string. Cost: y = 4 (since the removed characters, 'u' and 'i' are diff) Total cost --> x + y = 2 + 4 = 6