You are given a tree with N nodes numbered 0..N-1. Each node holds the letter 'a' or 'b'. The tree is described by an array A of length N where A[k] is the parent of node k, with A[root] = -1. Letters are stored in a string S (S[k] is the letter of node k). Return the number of vertices on the longest path such that no two adjacent nodes on the path share the same letter.

Example

solution("ab", [-1, 0]) = 2
solution("abbab", [-1, 0, 0, 0, 2]) = 3

For S = "abbab", A = [-1, 0, 0, 0, 2], the longest alternating path is 1 — 0 — 2.

解法

树根固定后，节点 u DFS 每个孩子 v：取 v 处最长向下链；若 S[v] != S[u] 则可挂到 u。在 u 处合并最长的两条链更新答案(经过 u 的路径)，返回 top1 + 1 给父亲。复杂度 O(N)。

import sys
from collections import defaultdict

def solution(S: str, A: list[int]) -> int:
    n = len(A)
    if n == 1:
        return 1

    sys.setrecursionlimit(n + 100)

    children = defaultdict(list)
    root = -1
    for v, p in enumerate(A):
        if p == -1:
            root = v
        else:
            children[p].append(v)

    ans = 1

    def dfs(u: int) -> int:
        # returns longest valid chain ending at u (inclusive), extending downward
        nonlocal ans
        downs = []
        for v in children[u]:
            child_chain = dfs(v)
            if S[v] != S[u]:
                downs.append(child_chain)

        downs.sort(reverse=True)
        top1 = downs[0] if len(downs) >= 1 else 0
        top2 = downs[1] if len(downs) >= 2 else 0
        ans = max(ans, top1 + top2 + 1)

        return top1 + 1

    dfs(root)
    return ans

import java.util.*;

class Solution {
    String s;
    List<List<Integer>> children;
    int ans;

    int solution(String S, int[] A) {
        int n = A.length;
        if (n == 1) return 1;

        this.s = S;
        this.children = new ArrayList<>();
        for (int i = 0; i < n; i++) children.add(new ArrayList<>());

        int root = -1;
        for (int v = 0; v < n; v++) {
            if (A[v] == -1) root = v;
            else children.get(A[v]).add(v);
        }

        ans = 1;
        dfs(root);
        return ans;
    }

    // returns longest valid chain ending at u (inclusive)
    int dfs(int u) {
        List<Integer> downs = new ArrayList<>();
        for (int v : children.get(u)) {
            int childChain = dfs(v);
            if (s.charAt(v) != s.charAt(u)) {
                downs.add(childChain);
            }
        }

        downs.sort(Collections.reverseOrder());
        int top1 = downs.size() >= 1 ? downs.get(0) : 0;
        int top2 = downs.size() >= 2 ? downs.get(1) : 0;
        ans = Math.max(ans, top1 + top2 + 1);

        return top1 + 1;
    }
}

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

class Solution {
public:
    string s;
    vector<vector<int>> children;
    int ans;

    int solution(string S, vector<int>& A) {
        int n = A.size();
        if (n == 1) return 1;

        s = S;
        children.assign(n, {});
        int root = -1;
        for (int v = 0; v < n; v++) {
            if (A[v] == -1) root = v;
            else children[A[v]].push_back(v);
        }

        ans = 1;
        dfs(root);
        return ans;
    }

    // returns longest valid chain ending at u (inclusive)
    int dfs(int u) {
        vector<int> downs;
        for (int v : children[u]) {
            int childChain = dfs(v);
            if (s[v] != s[u]) downs.push_back(childChain);
        }

        sort(downs.begin(), downs.end(), greater<int>());
        int top1 = downs.size() >= 1 ? downs[0] : 0;
        int top2 = downs.size() >= 2 ? downs[1] : 0;
        ans = max(ans, top1 + top2 + 1);

        return top1 + 1;
    }
};

You are given two arrays A and B, each of length N. Build array C where for each index k, C[k] is either A[k] or B[k]. Choose values so the smallest positive integer missing from C is as small as possible — i.e. return the smallest positive integer that cannot occur in any merged C.

Example

solution([1, 2, 4, 3], [1, 3, 2, 3]) = 2
solution([3, 2, 1, 6, 5], [4, 2, 1, 3, 3]) = 3
solution([1, 2], [1, 2]) = 3

Constraints

1 ≤ N ≤ 10⁵, 1 ≤ A[i], B[i] ≤ 10⁵.

解法

建二分图：整数 v(1..N+1)连向 A 或 B 中包含 v 的下标。按 1, 2, ... 顺序用增广路(匈牙利算法)贪心匹配到不同下标，首个无法匹配的整数即答案。最坏 O(N²)，随机输入很快。

from collections import defaultdict

def solution(A: list[int], B: list[int]) -> int:
    n = len(A)
    positions = defaultdict(list)
    for k in range(n):
        positions[A[k]].append(k)
        if B[k] != A[k]:
            positions[B[k]].append(k)

    used = [None] * n
    assigned = {}

    def try_assign(v: int, visited: set) -> bool:
        for k in positions[v]:
            if k in visited:
                continue
            visited.add(k)
            if used[k] is None or try_assign(used[k], visited):
                used[k] = v
                assigned[v] = k
                return True
        return False

    for v in range(1, n + 2):
        if v not in positions:
            return v
        if not try_assign(v, set()):
            return v

    return n + 1

import java.util.*;

class Solution {
    Map<Integer, List<Integer>> positions;
    Integer[] used;

    int solution(int[] A, int[] B) {
        int n = A.length;
        positions = new HashMap<>();
        for (int k = 0; k < n; k++) {
            positions.computeIfAbsent(A[k], x -> new ArrayList<>()).add(k);
            if (B[k] != A[k]) {
                positions.computeIfAbsent(B[k], x -> new ArrayList<>()).add(k);
            }
        }

        used = new Integer[n];

        for (int v = 1; v <= n + 1; v++) {
            if (!positions.containsKey(v)) return v;
            Set<Integer> visited = new HashSet<>();
            if (!tryAssign(v, visited)) return v;
        }
        return n + 1;
    }

    boolean tryAssign(int v, Set<Integer> visited) {
        for (int k : positions.get(v)) {
            if (visited.contains(k)) continue;
            visited.add(k);
            if (used[k] == null || tryAssign(used[k], visited)) {
                used[k] = v;
                return true;
            }
        }
        return false;
    }
}

#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class Solution {
public:
    unordered_map<int, vector<int>> positions;
    vector<int> used;

    int solution(vector<int>& A, vector<int>& B) {
        int n = A.size();
        positions.clear();
        for (int k = 0; k < n; k++) {
            positions[A[k]].push_back(k);
            if (B[k] != A[k]) positions[B[k]].push_back(k);
        }

        used.assign(n, -1);

        for (int v = 1; v <= n + 1; v++) {
            if (positions.find(v) == positions.end()) return v;
            unordered_set<int> visited;
            if (!tryAssign(v, visited)) return v;
        }
        return n + 1;
    }

    bool tryAssign(int v, unordered_set<int>& visited) {
        for (int k : positions[v]) {
            if (visited.count(k)) continue;
            visited.insert(k);
            if (used[k] == -1 || tryAssign(used[k], visited)) {
                used[k] = v;
                return true;
            }
        }
        return false;
    }
};

You are given a string S. In one move you can erase any pair of identical letters from S. Find the shortest possible string achievable; among all such shortest strings, return the lexicographically smallest one.

Example

solution("CBCAAXA") = "BAX"
solution("ZYXZYZYV") = "XYZV" // length 4 cannot be shortened further with this exact spec
solution("ABCBACDDAB") = ""
solution("AKFKFNOGKFB") = "AFKMOGB"

Constraints

1 ≤ N ≤ 10⁵, S consists of uppercase letters.

解法

消除所有重复对后，偶数次出现的字母全部消失，奇数次出现的字母各保留一份。在所有合法顺序中取字典序最小：经典单调栈，从左到右扫，若栈顶大于当前字符且后面还有同样的字符就弹出。复杂度 O(N)。

def solution(S: str) -> str:
    n = len(S)
    total = [0] * 26
    for c in S:
        total[ord(c) - ord('A')] += 1

    # target[ch] = 1 means this letter must be kept exactly once
    target = [t % 2 for t in total]

    seen = [0] * 26
    in_stack = [False] * 26
    stack = []

    for i, c in enumerate(S):
        idx = ord(c) - ord('A')
        seen[idx] += 1

        if target[idx] == 0:
            continue
        if in_stack[idx]:
            continue

        # pop a larger top if the same letter still appears later
        while stack and stack[-1] > c:
            top_idx = ord(stack[-1]) - ord('A')
            remaining = total[top_idx] - seen[top_idx]
            if remaining >= 1:
                stack.pop()
                in_stack[top_idx] = False
            else:
                break

        stack.append(c)
        in_stack[idx] = True

    return ''.join(stack)

class Solution {
    String solution(String S) {
        int n = S.length();
        int[] total = new int[26];
        for (char c : S.toCharArray()) total[c - 'A']++;

        int[] target = new int[26];
        for (int i = 0; i < 26; i++) target[i] = total[i] % 2;

        int[] seen = new int[26];
        boolean[] inStack = new boolean[26];
        StringBuilder stack = new StringBuilder();

        for (int i = 0; i < n; i++) {
            char c = S.charAt(i);
            int idx = c - 'A';
            seen[idx]++;

            if (target[idx] == 0) continue;
            if (inStack[idx]) continue;

            while (stack.length() > 0 && stack.charAt(stack.length() - 1) > c) {
                char top = stack.charAt(stack.length() - 1);
                int topIdx = top - 'A';
                int remaining = total[topIdx] - seen[topIdx];
                if (remaining >= 1) {
                    stack.deleteCharAt(stack.length() - 1);
                    inStack[topIdx] = false;
                } else {
                    break;
                }
            }

            stack.append(c);
            inStack[idx] = true;
        }

        return stack.toString();
    }
}

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

class Solution {
public:
    string solution(string S) {
        int n = S.size();
        vector<int> total(26, 0);
        for (char c : S) total[c - 'A']++;

        vector<int> target(26);
        for (int i = 0; i < 26; i++) target[i] = total[i] % 2;

        vector<int> seen(26, 0);
        vector<bool> inStack(26, false);
        string stk;

        for (int i = 0; i < n; i++) {
            char c = S[i];
            int idx = c - 'A';
            seen[idx]++;

            if (target[idx] == 0) continue;
            if (inStack[idx]) continue;

            while (!stk.empty() && stk.back() > c) {
                char top = stk.back();
                int topIdx = top - 'A';
                int remaining = total[topIdx] - seen[topIdx];
                if (remaining >= 1) {
                    stk.pop_back();
                    inStack[topIdx] = false;
                } else {
                    break;
                }
            }

            stk.push_back(c);
            inStack[idx] = true;
        }

        return stk;
    }
};

A roll operation increments each character by one in a circular manner within the lowercase alphabet ('a' → 'b', ..., 'z' → 'a'). Given a string s and an array roll, for each i roll the first roll[i] characters of s once. Return the final string.

Example: s = "abz", roll = [3, 2, 1] → "dda".

• After roll[0] = 3: "abz" → "bca".
• After roll[1] = 2: "bca" → "cda".
• After roll[2] = 1: "cda" → "dda".

Constraints

1 ≤ |s| ≤ 10⁵, 1 ≤ n ≤ 10⁵, 1 ≤ roll[i] ≤ |s|.

Two interns must complete n tasks total. The first intern earns reward_1[i] for task i, the second earns reward_2[i]. Intern 1 must complete exactly k tasks; intern 2 takes the rest. Return the maximum total reward.

Example: n = 5, reward_1 = [5, 4, 3, 2, 1], reward_2 = [1, 2, 3, 4, 5], k = 3 → 21.

Constraints

1 ≤ n ≤ 10⁵, 0 ≤ k ≤ n, 1 ≤ reward_1[i], reward_2[i] ≤ 10⁴.

Given a lowercase string s, you may perform the operation: pick 1 ≤ i ≤ |s| − 2 such that s[i] == s[i+1] and s[i+1] != s[i+2], then replace s[i+2] with s[i]. Find the maximum number of operations.

Example: s = "aabaab" → 2. ("aabaab" → "aaaab" → "aaaaa", two valid steps.)

Constraints

3 ≤ |s| ≤ 2*10⁵, lowercase only.

A shopkeeper lays out items in a list. Starting from the left, each item is sold at its full price minus the price of the first item to its right whose price is ≤ its own. If no such item exists, the item sells at full price. Print the total sold cost and the 0-based indices of items sold at full price (ascending).

Example: prices = [2, 3, 1, 2, 4, 2] → total 8, full-price indices [2, 5].

Constraints

1 ≤ n ≤ 10⁵, 1 ≤ prices[i] ≤ 10⁸.

A retail store chain wants to expand into a new neighbourhood. To make the number of clients as large as possible, the new branch should be at a distance of no more than K from all the houses in the neighborhood. A is the matrix of size N * M. It represents the neighbourhood as a rectangular grid, in which each cell is an integer 0 (an empty plot) and 1 (a house). The distance between two cells is calculated as the minimum number of cell borders that one has to cross to move from the source cell to the target cell. It doesn't matter whether the cells on the way are empty or occupied, but it doesn't allow for moving through corners. A store can be built on an empty plot. How many suitable locations are there? Function Description Complete the function findSuitableLocations in the editor. findSuitableLocations has the following parameters:

• 1. int[][] A: a matrix representing the neighborhood
• 2. int K: the maximum distance from all houses Returns int: the number of empty plots close enough to all the houses

Constraints

N/A

You are given an undirected graph consisting of N vertices, numbered from 1 to N, and M edges. The graph is described by two arrays, A and B, both of length M. A pair (A[K], B[K]), for K from 0 to M-1, describes an edge between vertex A[K] and vertex B[K]. Your task is to assign all values from the range [1..N] to the vertices of the graph, giving one number to each of the vertices. Do it in such a way that the sum over all edges of the values at the edges' endpoints is maximal. Notice that the value assigned to vertex 5 did not have any effect on the final result as it is not an endpoint of any edge.

Constraints

N/A

Example 1

Input:

N = 5
A = [2, 1, 2]
B = [1, 3, 4, 4]

Output:

31

Explanation: In order to obtain the maximum sum of weights, you can assign the following values to the vertices: 3, 5, 2, 4, 1 (to vertices 1, 2, 3, 4, 5 respectively). This way we obtain the sum of values at all edges' endpoints equal to 7 + 8 + 7 + 9 = 31. edge (2, 3): 7 = 5 (vertex 2) + 2 (vertex 3) edge (2, 1): 8 = 5 (vertex 2) + 3 (vertex 1) edge (1, 4): 7 = 3 (vertex 1) + 4 (vertex 4) edge (2, 4): 9 = 5 (vertex 2) + 4 (vertex 4)

A game board consists of N+1 fields, numbered from 0 to N from left to right. One letter ("a" or "b") is written between every two adjacent fields. The letters on the board are described by a string L of length N, where L[K] (for K within the range [0..N-1]) is the letter between fields K and K+1. For example, given L = "aaabab" and N = 6, the game board at the beginning looks like this: a a a b a b 0 1 2 3 4 5 6 A game piece is placed at start. It can move left or right, flipping the letter it crosses ("a" → "b" and "b" → "a"). The objective is to find the minimum number of moves needed to balance the count of "a" and "b". If it's impossible, return -1 Write a function that, given a string L of length N and an integer start, returns the minimum number of moves such that, after those moves, there will be the same number of letters "a" and "b" on the board (or returns -1 if it is impossible).

Constraints

• N is an integer within the range [1..100].
• L is made only of the characters 'a' and/or 'b'.
• start is an integer within the range [0..N].

Example 1

Input:

L = "aaabab"
start = 0

Output:

1

Explanation: The game piece must move one field to the right. This way, the first letter of L will be switched to produce string "baabab". Both letters occur three times in this string.

Example 2

Input:

L = "aaabab"
start = 6

Output:

5

Explanation: The game piece has to move 5 times to the left: "aaabab" → "aaaaba" → "aaabba" → "aababa" → "aabbaa" → "abbbaa" Output: 5

Example 3

Input:

L = "ababa"
start = 1

Output:

-1

Explanation: It is impossible to equalize the number of letters "a" and "b". Output: -1

Example 4

Input:

L = "babbaa"
start = 2

Output:

0

Explanation: The number of letters "a" and "b" is already equal.

Given a list of integer-sized stacks of blocks, repeatedly convert pairs of blocks in the current stack into single blocks added to the next stack (carrying right). After processing, a stack keeps an odd block as "leftover", and the trailing carry forms additional leftover stacks of one block each. Return the total number of leftover stacks.

Example 1

Input:

stacks = [5, 3, 1]

Output:

4

Explanation: Following the given operations:

• 4 from the first stack can get converted into 2 to the next stack with one left over
• 2 + 3 = 5 which follows the same, one left over with the 4 converted into 2 for the next stack
• 2 + 1 = 3 which makes two blocks get converted into 1 into the next stack
• 1 + 0 = 1, no possible operation Thus, there are 4 stacks with 1 block leftover.

You are given an undirected graph consisting of N vertices, numbered from 1 to N, and M edges. The graph is described by two arrays, A and B, both of length M. A pair (A[K], B[K]) for K from 0 to M-1 describes an edge between vertex A[K] and vertex B[K]. Your task is to check whether the given graph contains a path from vertex 1 to vertex N going through all the vertices one by one in increasing order of their numbers. All connections on the path should be direct. Function Description Complete the function checkPathPresence in the editor. checkPathPresence has the following parameters:

• 1. N: an integer, the number of vertices
• 2. int A[]: an array of integers representing one end of the edges
• 3. int B[]: an array of integers representing the other end of the edges Returns int: 1 if true there is a path from vertex 1 to vertex N going through all the vertices in increasing order, otherwise 0 (false)

Example 1

Input:

N = 4
A = [1, 2, 4, 4, 3]
B = [2, 3, 1, 3, 1]

Output:

1

Explanation: There is a path 1-2-3-4 using the edges (1,2), (2,3), and (4,3).

There is a cleaning robot which is cleaning a rectangular grid of size N x M, represented by array R consisting of N strings. Rows are numbered from 0 to N-1 (from top to bottom) and columns are numbered from 0 to M-1 (from left to right). The robot starts cleaning in the top-left corner, facing rightwards. It moves in a straight line for as long as it can, in other words, while there is an unoccupied grid square ahead of it. When it cannot move forward, it rotates 90 degrees clockwise and tries to move forward again until it encounters another obstacle, and so on. Dots in the array (".") represent empty squares and "X"s represent occupied squares (ones the robot cannot move through). Each square that the robot occupied at least once is considered clean. The robot moves indefinitely. Function Description Write a function: public int cleaningBot (String[] R) that, given an array R consisting of N strings, each of length M. representing the grid, returns the number of clean squares.

Constraints

• 1 ≤ N, M ≤ 1000
• 每个格子是 '.' 或 'X'

Example 1

Input:

R = ["...X..", "....XX", "..X..."]

Output:

6

Explanation:

Strings with long blocks of repeating characters take much less space if kept in a compressed representation. To obtain the compressed representation, we replace each segment of equal characters in the string with the number of characters in the segment followed by the character (for example, we replace segment "CCCC" with "4C"). To avoid increasing the size, we leave the one-letter segments unchanged (the compressed representation of "BC" is the same string - "BC". For example, the compressed representation of the string "ABBBCDDCCC" is "A3B2C2D3C", and the compressed representation of the string "AAAAAAAAAAABXXAAAAAAAAAA" is "11AB2X10A". Observe that, in the second example, if we removed the "BXX" segment from the middle of the word, we would obtain a much shorter compressed representation - "21A". In order to take advantage of this observation, we decided to modify our compression algorithm. Now, before compression, we remove exactly K consecutive letters from the input string. We would like to know the shortest compressed form that we can generate this way. Given a string S of length N and an integer K, returns the shortest possible length of the compressed representation of S after removing exactly K consecutive characters from S.

Example 1

Input:

s = "ABBBCCDDCCC"
k = 3

Output:

5

Explanation: (Remove DDC → A3B4C)

Example 2

Input:

s = "ABCDDDCEFG"
k = 2

Output:

6

Explanation: (Remove EF → ABC3DG)

There are n people in a row. The height of the i-th person is a[i]. You can choose any subset of these people and try to arrange them into a balanced circle. A balanced circle is such an order of people that the difference between heights of any adjacent people is no more than 1. For example, let heights of chosen people be [a[i1], a[i2], ..., a[ik]], where k is the number of people you choose. Then the condition |a[ij] - a[ij+1]| ≤ 1 should be satisfied for all j from 1 to k - 1 and the condition |a[i1] - a[ik]| ≤ 1 should be also satisfied. |x| means the absolute value of x. It is obvious that the circle consisting of one person is balanced. Your task is to choose the maximum number of people and construct a balanced circle consisting of all chosen people. It is obvious that the circle consisting of one person is balanced so the answer always exists. Input The first line of the input contains one integer n (1 ≤ n ≤ 2 · 10⁵) — the number of people. The second line of the input contains n integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 2 · 10⁵), where a[i] is the height of the i-th person. Output In the first line of the output print k — the number of people in the maximum balanced circle. In the second line print k integers res[1], res[2], ..., res[k], where res[j] is the height of the j-th person in the maximum balanced circle. The condition |res[j] - res[j+1]| ≤ 1 should be satisfied for all j from 1 to k - 1 and the condition |res[1] - res[k]| ≤ 1 should be also satisfied.

Constraints

N/A

Example 1

Input:

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

Output:

[2, 1, 1, 2, 3]

Explanation: N/A

Example 2

Input:

heights = [3, 7, 5, 1, 5]

Output:

[5, 5]

Explanation: N/A

Example 3

Input:

heights = [5, 1, 4]

Output:

[4, 5]

Explanation: N/A

Example 4

Input:

heights = [2, 2, 3, 2, 1, 2, 2]

Output:

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

Explanation: N/A

Given a string s, return the number of distinct lowercase letters that appear strictly before the first uppercase letter in s. If s has no uppercase letter, return the number of distinct lowercase letters in the whole string.

Example 1

Input:

s = "aaAbcCABBc"

Output:

2

Explanation: Here the output is 2, a and b, c iss not counted.

A string s, is similar to another string t, if it possible to swap two adjacent characters at most once in s to turn it into t. Given a keyword string named key, find how many substrings of text are similar to key.

Constraints

• key and text will consist solely of lowercase English letters.
• 1 ≤ |key| ≤ |text| ≤ 50, where |s| denotes the length of a string s.

Example 1

Input:

key = "moon"
text = "monomon"

Output:

2

Explanation: Consider the first four characters in text. i.e "mono". Swap the last two characters to match the keyword "moon". The last four characters in the text are "omon". Swap the first two characters to match the keyword. Thus, there are 2 substrings of "monomon" that are similar to "moon". Note, that no other substring is similar to the given key.

Example 2

Input:

key = "aaa"
text = "aaaa"

Output:

2

Explanation: There are 2 substrings of "aaaa" that are similar to "aaa" are:

• aaaa
• aaaa

Example 3

Input:

key = "xxy"
text = "zxxyxyx"

Output:

3

Explanation: No explanation is provided for now

Given an array of positive integers arr, count the number of contiguous subarrays whose bitwise OR of all elements is equal to some element that appears in arr.

Example 1

Input:

arr = [1, 6, 7]

Output:

5

Explanation:

Example 2

Input:

arr = [2, 4, 7]

Output:

5

Explanation:

There are N holes arranged in a row in the top of an old table. We want to fix the table by covering the holes with two boards. For technical reasons, the boards need to be of the same length. The position of the K-th hole is A[K]. What is the shortest length of the boards required to cover all the holes? The length of the boards has to be a positive integer. A board of length L, set at position X, covers all the holes located between positions X and X+L (inclusive). The position of every hole is unique. Complete the func in the editor which, given an array A of integers of length N, representing the positions of the holes in the table, returns the shortest board length required to cover all the holes.

Constraints

• N is an integer within the range [1..100,000]
• each element of array A is an integer within the range 0..1,000,000,000
• the elements of A are all distinct

Example 1

Input:

A = [11, 20, 15]

Output:

4

Explanation: The first board would cover the holes in positions 11 and 15, and the second board the hole at position 20.

Example 2

Input:

A = [15, 20, 9, 11]

Output:

5

Explanation: The first board covers the holes at positions 9 and 11, and the second one the holes in positions 15 and 20.

Example 3

Input:

A = [0, 44, 32, 30, 42, 18, 34, 16, 35]

Output:

18

Explanation: The first board would cover the holes in positions between 0 and 18, and the second the positions between 30 and 44.

Example 4

Input:

A = [9]

Output:

1

Explanation: There is only one hole, so the board length required is 1.

You are given two arrays A and B consisting of N integers each. Index K is named fair if the four sums A[0]+...A[K-1]), A[K]+...+A[N-1]), B[0]+...+B[K-1]) and B[K]+...+B[N-1]) are all equal. In other words, K is the index where the two arrays, A and B, can be split (into two non-empty arrays each) in such a way that the sums of the resulting arrays' elements are equal. For example, given arrays A = [4,-1, 0, 3] and B = [-2, 5, 0, 3], index K = 2 is fair. The sums of the subarrays are all equal: 4+(-1) = 3; 0+3 = 3; -2 + 5 = 3 and 0 + 3 = 3.

Example 1

Input:

A = [4,-1,0,3]
B = [-2,5,0,3]

Output:

2

Explanation: Index K = 2 is fair. The sums of the subarrays are all equal: 4+(-1) = 3; 0+3 = 3; -2 + 5 = 3 and 0 + 3 = 3.

Example 2

Input:

A = [2,-2,-3,3]
B = [0,0,4,-4]

Output:

1

Explanation: Index K = 1 is fair. The sums of the subarrays are all equal: 2 = 2; -2+(-3)+3 = 0; 0 = 0; 0+4+(-4) = 0.

Example 3

Input:

A = [4,-1,0,3]
B = [-2,6,0,4]

Output:

0

Explanation: There is no fair index K in this case.

Example 4

Input:

A = [1,4,2,-2,5]
B = [7,-2,-2,2,5]

Output:

2

Explanation: Index K = 2 is fair. The sums of the subarrays are all equal: 1+4 = 5; 2+(-2)+5 = 5; 7+(-2) = 5; (-2)+2+5 = 5.

The uniqueness of an array of integers is defined as the number of distinct elements present. For example, the uniqueness of [1, 5, 2, 1, 3, 5] is 4, element values 1, 2, 3, and 5. For an array arr of n integers, the uniqueness values of its subarrays is generated and stored in another array, call it subarray_uniqueness. Notes: The median of a list is defined as the middle value of the list when it is sorted in non-decreasing order. If there are multiple choices for median, the smaller of the two values is taken. For example, the median of [1, 5, 8] is 5, and [2, 3, 7, 11] is 3. A subarray is a contiguous part of the array. For example, [1, 2, 3] is a subarray of [6, 1, 2, 3, 5] but [6, 2] is not. Function Description Complete the function findArrayUniquenessMedian in the editor. findArrayUniquenessMedian has the following parameter:

• int[] arr: an array of integers Returns int: the median of the uniqueness values of all subarrays of arr

Constraints

• 1 ≤ arr.length ≤ 10⁵
• 1 ≤ arr[i] ≤ 10⁹

Example 1

Input:

arr = [1, 2, 1]

Output:

1

Explanation: There are n = 3 elements in arr = [1, 2, 1]. The subarrays along with their uniqueness values are:

• [1]: uniqueness = 1
• [1, 2]: uniqueness = 2
• [1, 2, 1]: uniqueness = 2
• [2]: uniqueness = 1
• [2, 1]: uniqueness = 2
• [1]: uniqueness = 1 The subarray_uniqueness array is [1, 2, 2, 1, 2, 1]. After sorting, the array is [1, 1, 1, 2, 2, 2]. The choice is between the two bold values. Return the minimum of the two, 1. Output: 1

Example 2

Input:

arr = [1, 2, 3]

Output:

1

Explanation: arr = [1, 2, 3]

• [1]: uniqueness = 1
• [1, 2]: uniqueness = 2
• [1, 2, 3]: uniqueness = 3
• [2]: uniqueness = 1
• [2, 3]: uniqueness = 2
• [3]: uniqueness = 1 After sorting, the array is [1, 1, 1, 2, 2, 3]. Output: 1.

(no statement available)

Example 1

Input:

nums = [2, 36, 45, 306, 415]

Output:

460

Explanation: The maximum sum of any 2 numbers whose first and last digits match is obtained by adding 45 and 415, which gives us 460.

You are presented with a two-dimensional grid of size N x M (N rows and M columns). Each cell in the grid is either black ("B") or white ("w"). A row or column is considered symmetric if it reads the same forwards as it does backward. For example, a row "BWWBWWB" is symmetric whereas "WBWB" isn't. The same symmetry criterion applies to columns. In one move, you can change the color in a single cell to the opposite. Your task is to determine the minimum number of moves required to make every row and column in the grid symmetric. Given an array grid consisting of N strings, all of length M (each string is a single row of the grid), returns the minimum number of moves required to make all rows and columns symmetric.

Constraints

N/A

Example 1

Input:

grid = ["BBWWB", "WWWBW", "BWWWW"]

Output:

3

Explanation: No explanation for now

Example 2

Input:

grid = ["BBBB", "WWWW", "BBWB", "WWWW"]

Output:

7

Explanation: No explanation for now

Example 3

Input:

grid = ["BWB", "WBB", "WBW"]

Output:

4

Explanation: No explanation for now

You are given a list of houses, such that A[k] corresponds to the amount of energy needed for house k. You will be installing two types of solar panels:

• Type 1: A solar panel which provides A[k] amount of power for price X.
• Type 2: A solar panel which provides 2 * A[k] amount of power for price Y. Your goal is to find the minimum cost such that all houses are provided with at least their required amount of power. Note: The power distributed from Y is not sequential, as you only focus on providing at least the net amount of energy of all the houses.

Example 1

Input:

A = [4, 3, 5, 2]
X = 2
Y = 5

Output:

7

Explanation: Assign solar panel type Y to A[2], which will cover A[1] and A[3], and then assign solar panel type X to A[0]. Thus the minimum cost is 5 + 2 = 7.

Given an array blocks where each cell represents the height o

Constraints

N/A

Example 1

Input:

blocks = [9,2,5,3,0]

Output:

2

Explanation: Let the two frogs start on cell 4 and one of them go to cell 2. (There is another option here that will give you 2).

Example 2

Input:

blocks = [1,2,3,4,5,8]

Output:

6

Explanation: If both frogs start at cell 5.

Given a string S consisting of N chars, return the alphabetically smallest string that can be obtained by removing exactly one letter from S.

Constraints

• N is an integer within the range [2...100,000]
• string S is made only of lowercase letters (a-z)

Example 1

Input:

S = "acb"

Output:

"ab"

Explanation: By removing 1 letter, you will obtain "ac", "ab", or "cb". Your function should return "ab" (After removing 'c') since it is a alphabetically smaller than "ac" and "bc" :)

Example 2

Input:

S = "hot"

Output:

"ho"

Explanation: "ho" is alphabetically smaller than "ht" and "ot"

Example 3

Input:

S = "codility"

Output:

"cdility"

Explanation: Obtain the answer by removing the second letter.

Example 4

Input:

S = "aaaa"

Output:

"aaa"

Explanation: Any occurrence of 'a' can be removed.

Before optimizing operating system resource management, resources are distributed across n system locations. The objective is to consolidate them into a maximum of k locations. The cost associated with relocating all the resources from location i to another location j is determined by the value costToTransfer[i][j], the computational overhead required. The overall cost is the sum of the resource transfers. Locations are numbered from 0 to n - 1. Determine the minimum cost required to consolidate the resources to k locations. Note: A resource can be transferred from location to location through an intermediate location k. For an array of n integers, arr[n], perform the following operation up to some integer k times. Choose an index i such that 1 ≤ i ≤ n. Choose an index i such that 1 ≤ i ≤ n Replace arr[i] with arr[i] * 2 The or-sum is the bitwise-or of all elements in the final array after the operations. Return the maximum or-sum possible. Function Description Complete the function getMaxOrSum in the editor. getMaxOrSum has the following parameters:

• int arr[n]: the original array
• int k: the maximum number of operations Returns int: the maximum or-sum possible

Example 1

Input:

arr = [12, 9]
k = 1

Output:

30

Explanation: These outcomes are possible after 1 operation. Select i = 1: The final array is arr = [24, 9]. Its or-sum is 25. Select i = 2: The final array is arr = [12, 18]. Its or-sum is 30. Of these, 30 is the greater or-sum. Return 30.

A student at HackerSchool is provided with a schedule of n days, where each day can have up to m hours of lecture classes. The schedule is represented by a binary matrix schedule[][], where schedule[i][j] = '1' means there is a lecture at the jth hour of the ith day, and schedule[i][j] = '0' means there is no lecture at that time. If the student attends the first lecture at the xth hour and the last lecture at the yth hour on a single day, then they spend (y - x + 1) hours at school that day. The student is allowed to skip up to k lectures in total over all n days. Determine the minimum total time (in hours) the student needs to attend school over all n days, given that they can skip lectures optimally. Function Description Complete the function getMinimumTime in the editor with the following parameters:

• char schedule[n][m]: binary strings each of length m, which denote the schedule of the school
• int k: the number of lectures the student can skip Returns int: the minimum total time the student is required to attend the school.

Constraints

• 1 ≤ k, m, n ≤ 200
• schedule[i][j] == '0' or '1'
• It is guaranteed that the length of each schedule[i] (0 ≤ i < n) is equal to m.

Example 1

Input:

schedule = [["10001"]]
k = 1

Output:

1

Explanation: The student can skip the last lecture of the first day, that is, schedule[0][4]. Then, they only have to attend one lecture at the 0th hour, so the total time spent at school = 1, which is the minimum possible. Thus, the answer is 1.

You are given an array A of length N. A subsequence is said to be great if the GCD of its elements is strictly greater than 1. The empty subsequence is not great.

You are given Q queries, each of the form (X, Y) (1-indexed): replace A[X] with Y. After each query, count the number of great subsequences of the current A modulo 10⁹ + 7. Return the sum of those per-query counts.

Constraints

1 ≤ N ≤ 10⁵ 1 ≤ A[i] ≤ 10⁵ 1 ≤ Q ≤ 10⁵ 2 ≤ P ≤ 2 1 ≤ queries[i][j] ≤ 10⁵

Example 1

Input:

A = [1, 2]
queries = [[1, 2]]

Output:

3

Explanation: Given N=2, A=[1,2], Q=1, P=2, queries=[(1,2)] After the first query, the subsequences are [2, 2], [2] and [2]. All of these GCD is more than 1. So, answer is 3.

Example 2

Input:

A = [1, 2, 3]
queries = [[1, 3], [2, 3]]

Output:

11

Explanation: Given N=3, A=[1,2,3], Q=2, P=2, queries=[(1,3), (2,3)] After query 1, A become [3,2,3], then good subsequences are [2],[3],[3],[3,3]. After query 2, A become [3,3,3], then good subsequences are [3],[3],[3],[3,3],[3,3],[3,3],[3,3,3] So, answer is 4+7=11.

Example 3

Input:

A = [2, 2, 2, 2, 2]
queries = [[1, 1], [2, 1]]

Output:

22

Explanation: Given N=5, A=[2,2,2,2,2], Q=2, P=2, queries=[(1,1), (2,1)] After query 1, A = [1,2,2,2,2], then total number of good subsequences is 15. After query 2, total number of good sequence is 7. Hence, the answer is 15+7=22.

There are N clients who have ordered N handmade items. The K-th client ordered exactly one item that takes T[K] hours to make. There is only one employee who makes items for clients, and they work in the following manner: spend one hour making the first item; if the item is finished, the employee delivers it to the client immediately; if the item is not finished, they put it after the N-th item for further work; the employee starts making the next item. As the result may be large, return its last nine digits without leading zeros (in other words, return the result modulo 10⁹). Function Description Complete the func in the editor that, given an array of integers T of length N, returns the total time that the clients need to wait (modulo 10⁹).

Constraints

• N is an integer within the range [1..100,000]
• each element of array T is an integer within the range [1..10,000]

Example 1

Input:

T = [3, 1, 2]

Output:

13

Explanation: The employee spends 6 hours making items in the following order: [1, 2, 3, 1, 3, 1]. The first client waited 6 hours for their item, the second client received their item after 2 hours and the third client after 5 hours. The total waiting time of all clients is 6 + 2 + 5 = 13.

Example 2

Input:

T = [1, 2, 3, 4]

Output:

24

Explanation: The employee prepares the items in the following order: 1, 2, 3, 4, 2, 3, 4, 3, 4, 4. The first client waited for 1 hour, the second client for 5 hours, the third client for 8 hours, and the fourth client for 10 hours. The total waiting time of all clients is 1 + 5 + 8 + 10 = 24 hours.

Example 3

Input:

T = [7, 7, 7]

Output:

60

Explanation: No explanation provided

Example 4

Input:

T = [10000]

Output:

10000

Explanation: No explanation provided

• Round 1: Word Pattern II
• Round 2: Implement Queue using Stacks
• Round 3: Island Perimeter I highly recommend to go to LC to solve this quesiton.. Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty). Implement the MyQueue class:
• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise. Notes:
• You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations. Wallz carries one more time!

Constraints

• 1 ≤ x ≤ 9
• At most 100 calls will be made to push, pop, peek, and empty.
• All the calls to pop and peek are valid.

Example 1

Input:

operations = ["MyQueue", "push", "push", "peek", "pop", "empty"]
arguments = [[], [1], [2], [], [], []]

Output:

[null, null, null, 1, 1, false]

Explanation: MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false

Implement a small in-memory table engine that begins with a CSV string and then executes a sequence of SQL-like commands. The first row of the CSV contains column names. Remaining rows contain data. Fields are comma-separated; quoted fields may contain commas and escaped double quotes. Support the following commands:

• SELECT col1,col2,... WHERE col=value: return matching rows with the selected columns joined by commas
• INSERT value1,value2,...: append one row
• DELETE WHERE col=value: delete every matching row Process commands in order and return every output row produced by the SELECT commands. Function Description Complete the function runInMemorySql in the editor below. runInMemorySql has the following parameters:
• String csv: the initial table contents
• String[] commands: the commands to execute in order Returns String[]: the output rows produced by all SELECT commands, in order.

Constraints

• The total number of rows plus commands can be as large as 10⁵.
• Quoted CSV fields may contain commas and doubled quotes.
• Only equality filters are required for this problem version.

• Round 1: Word Pattern II
• Round 2: Implement Queue using Stacks
• Round 3: Island Perimeter You are given row × col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island. Function Description Complete the function islandPerimeter in the editor. islandPerimeter has the following parameter:
• int[][] grid: a 2D array of integers Returns int: the perimeter of the island Wallz carries all!

Constraints

• row == grid.length
• col == grid[i].length
• `1

You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1. You are also given a string s of length n, where s[i] is the character assigned to node i. Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.

Constraints

• n == parent.length == s.length
• 1 = 1
• parent[0] == -1
• parent represents a valid tree.
• s consists of only lowercase English letters.

Example 1

Input:

parent = [-1,0,0,1,1,2]
s = "abacbe"

Output:

3

Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned. It can be proven that there is no longer path that satisfies the conditions.

Example 2

Input:

parent = [-1,0,0,0]
s = "aabc"

Output:

3

Explanation: The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.

You are given an array A consisting of N numbers. In one move you can delete either the first two, the last two, or the first and last elements of A. No move can be performed if the length of A is smaller than 2. The result of each move is the sum of the deleted elements. Given an array A of N integers, returns the maximum number of moves that can be performed on A, such that all performed moves have the same result.

Constraints

• N is an integer within the range [1..1,000];
• each element of array A is an integer within the range [1..1,000,000,000].

Example 1

Input:

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

Output:

3

Explanation: The first move should delete two last elements (4 and 2 with sum = 6), then A = [3, 1, 5, 3, 3]. The second move may delete first and last elements (3 and 3 with sum = 6), then A = [1, 5, 3]. The third move should delete first two elements (1 and 5 with sum = 6), then A = [3].

Example 2

Input:

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

Output:

4

Explanation: It is possible to delete the first and last elements four times, as each such pair of elements sums up to 6.

Example 3

Input:

A = [1, 9, 1, 1, 1, 1, 1, 1, 8, 1]

Output:

1

Explanation: There is no way to perform move that results with the same sum more than once.

Example 4

Input:

A = [1, 9, 8, 9, 5, 1, 2]

Output:

3

Explanation: The first move should delete the first two elements, then the second and third moves should delete first and last elements twice.

Example 5

Input:

A = [1, 1, 2, 3, 1, 2, 2, 1, 1, 2]

Output:

4

Explanation: One of the possible sequence of moves goes as follows: twice delete the last two elements, then delete the first and last elements, last move deletes the first two elements.

A car manufacturer has data about the production processes of N different cars (numbered from 0 to N-1) and wants to maximize the number of cars produced in the upcoming month. The manufacturing information is described by an array H, where H[K] denotes the number of hours required to produce the K-th car. There are two assembly lines in the factory, the first of which works for X, and the second Y, hours in a month. Every car can be constructed using either one of these lines. Only one car at a time can be produced on each assembly line and it is not possible to switch lines after starting the car's production. What is the maximum number of different cars that can be produced in the upcoming month? Function Description Write a function: class Solution { public int solution(int[] H, int X, int Y); } that, given an array H of N integers and two integers X and Y, returns the maximum number of different cars that can be produced in the upcoming month by assigning cars to assembly lines in an optimal way.

Constraints

• N is an integer within the range [1..1,000];
• each element of array H is an integer within the range [1..1,000];
• X and Y are integers within the range [1..500].

Example 1

Input:

H = [1, 1, 3]
X = 1
Y = 1

Output:

2

Explanation: Only cars whose assembly time requires 1 hour can be constructed.

Example 2

Input:

H = [6, 5, 5, 4, 3]
X = 8
Y = 9

Output:

4

Explanation: The cars that need 3 and 5 hours can be produced on the first assembly line while the second car that needs 5 hours and the car that needs 4 hours can be produced using the second line.

Example 3

Input:

H = [6, 5, 2, 1, 8]
X = 17
Y = 5

Output:

5

Explanation: The car that needs 5 hours can be produced on the second line and the four other cars can be produced on the first line.

Example 4

Input:

H = [5, 5, 4, 6]
X = 8
Y = 8

Output:

2

Explanation: Only one car can be produced on each line.

A technology company announced that a new supply of P monitors would soon be available at their store. There were N orders (numbered from 0 to N-1) placed by customers who wanted to buy those monitors. The K-th order has to be delivered to a location at distance D[K] from the store and is for exactly C[K] monitors. Now the time has come for the monitors to be delivered. The orders will be fulfilled one by one. To minimize the shipping time, it has been decided that the deliveries will be made in order of increasing distance from the store. If there are many customers at the same distance, they can be processed in any order. Monitors to more distant customers will be delivered only once all orders to customers closer to the store have already been fulfilled. What is the maximum total number of orders that can be fulfilled? Function Description Write a function: class Solution { public int solution(int[] D, int[] C, int P); } that, given two arrays of integers D and C, and an integer P, returns the maximum total number of orders that can be fulfilled.

Constraints

• N is an integer within the range [1..100,000].
• Each element of arrays D and C is an integer within the range [1..1,000,000,000].
• P is an integer within the range [0...10,000,000,000].

Example 1

Input:

D = [5, 11, 1, 3]
C = [6, 1, 3, 2]
P = 7

Output:

2

Explanation: The customers at distances 1 and 3 will have their orders fulfilled and 3 + 2 = 5 monitors will be delivered.

Example 2

Input:

D = [10, 15, 1]
C = [10, 1, 2]
P = 3

Output:

1

Explanation: Only the order for the customer at distance 1 will be fulfilled. There will not be enough monitors in the store for the customer at distance 10. Therefore, orders for customers at distances 10 and 15 will not be fulfilled.

Example 3

Input:

D = [11, 18, 1]
C = [9, 18, 8]
P = 7

Output:

0

Explanation: There are not enough monitors to fulfill any orders.

Example 4

Input:

D = [1, 4, 2, 5]
C = [4, 9, 2, 3]
P = 19

Output:

4

Explanation: All orders can be fulfilled as there are enough monitors available.

You are given a matrix A representing a chessboard with N rows and M columns. Each square of the chessboard contains an integer representing a points-based score. You have to place two rooks on the chessboard in such a way that they cannot attack each other and the sum of points on their squares is maximal. Rooks in chess can attack each other only if they are in the same row or column. Your task is to find the maximum sum of two squares of the chessboards on which the rooks can be placed. We cannot, for example, place the rooks at A[0][1] and A[1][1] (whose sum is 7), as they would attack each other. Function Description Write a function: class Solution { public int solution(int[][] A); } which, given a matrix A, returns the maximum sum that can be achieved by placing two non-attacking rooks.

Example 1

Input:

A = [[0, 1], [1, 4], [1, 2, 3]]

Output:

6

Explanation: We can place rooks in two different ways:

• One rook on A[0][0] = 1 and another rook on A[1][1] = 3. The sum of points on these squares is 4.
• One rook on A[0][1] = 4 and another rook on A[1][0] = 2. The sum of points on these squares is 6. In the example above, the answer is 6.

There is an array A of N integers which may contain positive and negative values. Choose two fragments, one of length K and one of length L, to maximize the sum of the elements that belong to the chosen fragments. However, if any individual element belongs to both fragments at the same time, each such element is added to the final sum only once and with a changed sign (i.e., negative values become positive values, and vice versa). Write a function: def solution(A, K, L) that, given an array A of N integers and integers K and L, returns the maximum total sum that can be obtained.

Example 1

Input:

A = [1, 3, -4, 2, -1]
K = 3
L = 2

Output:

10

Explanation: For A = [1, 3, -4, 2, -1], K = 3, L = 2, you can choose fragment [1, 3, -4] and fragment [-4, 2]. The third element of A belongs to both fragments, so the function should return 1 + 3 + -(-4) + 2 = 10.

Example 2

Input:

A = [-5, -3, -4]
K = 1
L = 3

Output:

-2

Explanation: For A = [-5, -3, -4], K = 1, L = 3, the segment of length L will contain each element of A. Then choosing -5 as the only element of the K segment will change its sign in the final sum. The function should return -2.

A storeroom is used to organize items stored in it on N shelves. Shelves are numbered from 0 to N-1. The K-th shelf is dedicated to items of only one type, denoted by a positive integer A[K]. Recently it was decided that it is necessary to free R consecutive shelves. Shelves cannot be reordered. What is the maximum number of types of items that can still be stored in the storeroom after freeing R consecutive shelves? Given: an array A of N integers representing types of items stored on storeroom shelves. an integer R representing the number of consecutive shelves to be freed. Returns the maximum number of different types of items that can be stored in the storeroom after freeing R consecutive shelves.

Constraints

• N is an integer within the range [1..100,000].
• R is an integer within the range [1..N].
• Each element of array A is an integer within the range [1..100,000].

Example 1

Input:

A = [2, 1, 2, 3, 2, 3, 2]
R = 3

Output:

2

Explanation: It can be achieved by freeing shelves 2, 3, 4. The remaining shelves contain item types {2, 3}.

Example 2

Input:

A = [2, 3, 1, 1, 2]
R = 2

Output:

3

Explanation: All three types {2, 3, 1} can still be stored by freeing the last two shelves.

Example 3

Input:

A = [20, 10, 10, 10, 30, 20]
R = 3

Output:

3

Explanation: It can be achieved by freeing the first three shelves. The remaining item types are {10, 30, 20}.

Example 4

Input:

A = [1, 100000, 1]
R = 3

Output:

0

Explanation: All shelves need to be freed, leaving no items.

Given an array A of integers (size N, divisible by 3) and an integer K representing the maximum number of moves allowed, you can increase or decrease any element in A by 1 per move. The goal is to maximize the difference between the N/3-th largest and N/3-th smallest elements in A after using up to K moves. Function Description Complete the function maximizeDifference in the editor. maximizeDifference has the following parameters:

• 1. int[] A: an array of integers
• 2. int K: the maximum number of moves allowed Returns int: the maximum difference that can be achieved

Constraints

• N is an integer within [3..150,000], divisible by 3.
• K is an integer within [0..500,000,000].
• Each element of A is an integer within [-300,000,000..300,000,000].

Example 1

Input:

A = [8, 8, 8, 7, 7, 7, 7, 7, 7, 7, -8, -8]
K = 1

Output:

1

Explanation: No explanation is provided for now As always, I will add it once find any. Or if you happen to know about it, feel free to dm Groot! Many thanks in advance!

Example 2

Input:

A = [-5, 1, 1, 4, 4, 4, 7, 4, 6]
K = 6

Output:

7

Explanation: No explanation is provided for now As always, I will add it once find any. Or if you happen to know about it, feel free to dm Groot! Many thanks in advance!

Example 3

Input:

A = [-7, -6, -3, -2, -2, -2, -2, -2, -2, -2, -2, -1]
K = 5

Output:

3

Explanation: No explanation is provided for now As always, I will add it once find any. Or if you happen to know about it, feel free to dm Groot! Many thanks in advance!

Example 4

Input:

A = [6, 6, 6, 6, 6, 6]
K = 3

Output:

1

Explanation: No explanation is provided for now As always, I will add it once find any. Or if you happen to know about it, feel free to dm Groot! Many thanks in advance!

A map of village is split into a rectangular grid with N rows (numbered from 0 - N - 1) and M columns (numbered from 0 to M - 1). Establish at most two rice cultivation areas in the village, using only cells dedicated to this purpose. The map is described by an array of strings: the C-th character of the R-th string can be either '.', meaning that the square of land in the R-th row and C-th column is a place where rice cultivation can be established, or '#' if it is an agricultural building. The shape of the cultivation areas should be a narrow rectangle (vertical with one cell width or horizontal with one cell height). What is the maximum number of cells that can be used for cultivation by choosing at most two areas? Given an array of strings A, returns an integer: the maximum number of cells that can be used for cultivation by choosing at most two areas.

Constraints

• N is an integer within the range [1..500]
• all strings in A are of the same length M within the range [1..500]
• all strings in A consist only of the characters '.' and/or '#'

Given a String S representing positive digit containing n numbers, and given k ( number of moves), you can replace any number other then 5, return the maximun number possible within k moves

Constraints

• An integer N in the range [1..100,000] — the length of a string S
• An integer K in the range [0..100,000]
• A string S of length N consisting only of digits (0-9), with no leading zeros.
• Full constraints updated on 05-24-2025 :)

Example 1

Input:

s = "1839559"
k = 4

Output:

"5855555"

Explanation: This test case was added on 05-24-2025. You can find the relevant source ss in the Problem Source section below. Happy coding!

Example 2

Input:

s = "5567855"
k = 4

Output:

"IMPOSSIBLE"

Explanation: Becasue there are 3 digits in S that are not 5, so we cant do the 4th operation. This test case was added on 05-24-2025. You can find the relevant source ss in the Problem Source section below. Coding is fun!

Example 3

Input:

s = "165232"
k = 3

Output:

"555552"

Explanation: Becasue there are 3 digits in S that are not 5, so we cant do the 4th operation. This test case was added on 05-24-2025. You can find the relevant source ss in the Problem Source section below. Coding is fun! It comes from Source 2, but the expected output there seems to conflict with what’s shown in Source 1. Source 1 states the expected output is "565552".

Example 4

Input:

s = "165232"
k = 3

Output:

"565552"

Explanation: This test case comes from Source 1, but the expected output there seems to conflict with what’s shown in Source 2. Source 2 states the expected output is 555552.

There is an array A of N non-negative integers. Any two initial elements of A that are adjacent can be replaced with their merged equivalent. For example, given A = [2, 3, 15], pair (2, 3) can be replaced with 23, resulting in array [23, 15], and pair (3, 15) can be replaced with 315, resulting in array [2, 315]. The result of the merge cannot be merged any further, so we can't get 2315 in the example above. What is the maximum possible sum of elements of A after any number of merges? Write a function that, given an array A of N non-negative integers, returns the maximum sum of elements of A after any number of merges.

Constraints

• N is an integer within the range [1..10,000]
• Each element of array A is an integer within the range [0..200]

Example 1

Input:

A = [2, 2, 3, 5, 4, 0]

Output:

97

Explanation: We can merge elements of the following pairs: (2, 2), (3, 5) and (4, 0). This results in A = [22, 35, 40], which sums up to 97.

Example 2

Input:

A = [3, 19, 191, 91, 3]

Output:

20107

Explanation: We can merge elements of the following pairs: (19, 191) and (91, 3). This results in A = [3, 19191, 913], which sums up to 20107.

Example 3

Input:

A = [12, 6, 18, 10, 1, 0]

Output:

1946

Explanation: The merges should make A = [126, 1810, 10], which sums up to 1946.

Example 4

Input:

A = [2, 1, 0, 1, 2, 9, 1, 0]

Output:

124

Explanation: The merges should make A = [21, 0, 12, 91, 0], which sums up to 124.

Given a word, calculate the smallest number of lette

Constraints

• the length of string S is within the range [1..100,000]
• string S consists only of lower case letters (a-z)

Example 1

Input:

S = "banana"

Output:

3

Explanation: Because we can remove three letters (the 1st, 3rd and 6th) to get the word "aan", which is sorted. Pls note that it is not possible to remove fewer than 3 letters

A domino is a rectangular tile divided into two square parts. There are between 1 and 6 dots on each of the parts. There is an array A of length 2N, representing N dominoes. Dominoes are arranged in a line in the order in which they appear in array A. The number of dots on the left and the right parts of the K-th domino are A[2K] and A[2*K+1], respectively. For example, an array A = [2, 4, 1, 3, 4, 6, 2, 4, 1, 6] represents a sequence of five domino tiles: (2,4), (1,3), (4,6), (2,4), and (1,6). In a correct domino sequence, each pair of neighboring tiles should have the same number of dots on their adjacent parts. For example, tiles (2, 4) and (4, 6) form a correct domino sequence and tiles (2, 4) and (1, 3) do not. What is the minimum number of domino tiles that must be removed from the sequence so that the remaining tiles form a correct domino sequence? It is not allowed to reorder or rotate the dominoes. Function Description Given an array A representing a sequence of N domino tiles, returns the minimum number of tiles that must be removed so that the remaining tiles form a correct domino sequence.

In this task you are given two strings of digits that represent (possibly very large) integers. Your goal is to make those numbers as close to one another as possible. In other words, you want to minimize the absolute value of their difference. You can swap some of the corresponding digits (e.g. the first digit of the first number with the first digit of the second number, the second digit of the first number with the second digit of the second number, etc.). Swapping the digits is an extremely tiring task, so you want to make as few swaps as possible. Given two strings S and T, both of length N, returns the minimum number of swaps needed to minimize the difference between the two numbers represented by the input strings. Write an efficient algorithm for the following assumptions: lengths of S and T are equal and within the range [1..100,000]; S and T consist only of digits and no other characters; neither S nor T contain leading zeroes.

Example 1

Input:

S = "29162"
T = "10524"

Output:

2

Explanation: We can swap the second and the fourth digits and obtain "20122" and "19564". The difference between the numbers is 558 and the number of swaps is 2. One can easily check that the difference is the smallest possible. Note that we could obtain the same difference by swapping the first, third and fifth digits, but this solution requires three swaps.

There is a bridge and cars are queued up at the entry of the bridge. Each car has a weight and at once only two cars can go to the bridge. the cars enter and exit the bridge in the same order as given in the array. For example, initially the first two cars enter the bridge, then the first car leaves and the third car arrives, then second car leaves and fourth car arrives and so on. The bridge has a capacity and if the total weight of the cars on the bridge exceeds that capacity, it will break. We can remove as many cars from the queue as we want and the relative order of the rest of the cars will remain the same. Find the minimum number of cars to remove so that the bridge doesn't break.

Constraints

• The size of the array is up to 10⁵.
• The weight of each car is up to 10⁹.

Example 1

Input:

weights = [3, 5, 2, 6, 1]
capacity = 8

Output:

0

Explanation: Initially: Cars 3 and 5 enter the bridge. Combined weight: 3 + 5 = 8 (which is okay, doesn't exceed capacity). Car 3 leaves, Car 2 enters. Now on bridge: 5 and 2. Combined weight: 5 + 2 = 7 (okay). Car 5 leaves, Car 6 enters. Now on bridge: 2 and 6. Combined weight: 2 + 6 = 8 (okay). Car 2 leaves, Car 1 enters. Now on bridge: 6 and 1. Combined weight: 6 + 1 = 7 (okay). In this scenario, we didn't have to remove any cars, and the bridge never broke. So, the minimum number of cars to remove is 0.

Example 2

Input:

weights = [3, 7, 2, 6, 1]
capacity = 8

Output:

1

Explanation: Initial steps: Cars 3 and 7 enter. Weight: 3 + 7 = 10 > 8 → bridge breaks. So, we need to remove at least one car to prevent this. Which car should we remove? Option 1: Remove 7. Remaining sequence: [3, 2, 6, 1]. 3 and 2: 5 3 leaves, 6 enters: 2 and 6: 8 2 leaves, 1 enters: 6 and 1: 7 No breakage. Removed 1 car. Option 2: Remove 3. Remaining sequence: [7, 2, 6, 1]. 7 and 2: 9 > 8 → breaks. Doesn't work. Option 3: Remove other cars. For instance, remove 2. Sequence: [3, 7, 6, 1]. 3 and 7: 10 > 8 → breaks. Doesn't work. So, the best is to remove 7, resulting in removing 1 car. Hence, the minimum number is 1.

Given a 2D matrix with 2 rows and columns, containing only the characters 'R', 'W', '?', give the minimum replacements of '?' required to make the matrix balanced. The matrix would be balanced when it has equal number of 'W' and 'R' in all the rows and columns. E.g. - R1 - "WR???"; R2 - "R???W" - Balanced - R1 - "WR?W", R2 - "RW?W"; 4 replacements

Constraints

Standard Huge Constraints

Example 1

Input:

matrix = [['W', 'R', '?', '?', '?'], ['R', '?','?', '?', 'W']]

Output:

4

Explanation: The given matrix can be balanced by making the following replacements: Replace the first '?' in R1 with 'W' and the second '?' with 'R'. Replace the first '?' in R2 with 'W' and the second '?' with 'R'. This results in 4 replacements, making the matrix balanced with equal numbers of 'W' and 'R' in all rows and columns.

Giv

Constraints

N/A

Example 1

Input:

S = "word"

Output:

1

Explanation: The answer is 1 as "word" doesn't have any duplicates.

Example 2

Input:

S = "dddd"

Output:

4

Explanation: The answer is 4 as we can only form substrings "d", "d", "d", "d".

Example 3

Input:

S = "cycle"

Output:

2

Explanation: The answer is 2 as we can make substrings "cy" and "cle".

Given 2 balls Red and White, return the minum number of swaps required where we want to arrange all the red balls into consistent segment (in one move, you can swap adjacent ones) Given that S is "RW" repeated 100,000 times, your function should return -1, as the minimum number of swaps required exceeds 10⁹.

Constraints

• N is an integer in the range [1..100,000]
• The string S consists only of the characters 'R' and 'W'.
• Constraints updated in full on 05-24-2025

Example 1

Input:

colors = "WRRWR"

Output:

2

Explanation: Given S = "WRRWR", your function should return 2. We can move the last ball two positions to the left:

1. "WRRWR"
2. "WRRWW"
3. "WWRRW" This example originates from source 2, which conflicts with source 1. Source 1 lists the input as "WRRWRW" with an output of 2, whereas source 2 shows the input as S="WRRWR" and also gives an output of 2. This new test case was added on 05-24-2025 :) You can find the relevant source ss in the Problem Source section below.

Example 2

Input:

colors = "WWRWWWWWWWWWRWR"

Output:

4

Explanation: Given S = "WWRWWWWWWWWWRWR", your function should return 4. We can move the first and last red balls toward the middle red ball:

1. "WWRWWWWWWWWWRWR"
2. "WWWWWWWWWWWRRWR"
3. "WWWWWWWWWWWRRWR" This new test case was added on 05-24-2025 :) You can find the relevant source ss in the Problem Source section below.

Example 3

Input:

colors = "WWW"

Output:

0

Explanation: There are no red balls that need to be grouped together. This new test case was added on 05-24-2025 :) You can find the relevant source ss in the Problem Source section below.

Example 4

Input:

colors = "WRRWRW"

Output:

2

Explanation: This example originates from source 1, which conflicts with source 2. Source 1 lists the input as "WRRWRW" with an output of 2, whereas source 2 shows the input as S="WRRWR" and also gives an output of 2.

Let us consider an infinite sequence of stacks indexed from 0, and an exchange operation that removes two tokens from a stack and adds one token to the next stack. For example, lets assume there are two tokens on stack 0 and three on stack 1. Two tokens from stack 0 may be exchanged for one new token on stack 1. After that operation, there are four tokens on stack 1 that may be exchanged for two new tokens on stack 2. Finally, a new token may be added to stack 3 by exchanging two tokens from stack 2. This gives us: stacks 0, 1 and 2 empty, and stack 3 with one token. Given the heights of the first N stacks, find the minimum number of tokens that may remain after any number of exchange operations. You may assume that all of the tokens are identical. All uninitialized stacks are empty by default. Function Description Write a function: class Solution { public int solution(int[] A); } that, given an array A of N integers, representing the heights of the first N stacks in the sequence, returns the minimum number of tokens which may remain on the stacks after any number of exchange operations.

Example 1

Input:

A = [2, 3]

Output:

1

Explanation: Given A = [2, 3], the function should return 1, as explained above.

You are given a shuffled set of records. Record i has three fields: starts[i], ends[i], and payloads[i]. The records form exactly one chain. If record A has ends[A] == starts[B], then record A must appear immediately before record B in the chain. Order the records by this chaining rule and concatenate their payloads in that order. Function Description Complete the function concatenateOrderedPayloads in the editor below. concatenateOrderedPayloads has the following parameters:

• String[] starts: the start keys
• String[] ends: the end keys
• String[] payloads: the payload fragments Returns String: the concatenated payload string after ordering the chain.

Constraints

• 1 ≤ starts.length == ends.length == payloads.length ≤ 2 * 10⁵<

Example 1

Input:

starts = ["aaa", "bbb", "ccc"]
ends = ["bbb", "ccc", "ddd"]
payloads = ["2", "1", "3"]

Output:

"213"

Explanation: The only valid order is aaa -> bbb -> ccc -> ddd, so the payloads join as 2 + 1 + 3.

Example 2

Input:

starts = ["p"]
ends = ["q"]
payloads = ["X"]

Output:

"X"

Explanation: A single record is already ordered.

You are given two arrays, A and B, each made of N integers. They represent a grid with N columns and 2 rows, where A is the upper row and B is the lower row. Your task is to go from the upper-left cell (represented by A[0]) to the bottom-right cell (represented by B[N-1]) moving only right and down, so that the maximum value over which you pass is as small as possible. Given two arrays of integers, A and B, of length N, returns the maximum value on the optimal path.

Example 1

Input:

A = [3, 4, 6]
B = [6, 5, 4]

Output:

5

Explanation: The optimal path is 3 → 4 → 5 → 4.

Example 2

Input:

A = [1, 2, 1, 1, 1, 4]
B = [1, 1, 1, 3, 1, 1]

Output:

2

Explanation:

Prepare a notification of the given message which will be displayed on a mobile device. The message is made of words separated by single spaces. The length of the notification is limited to K characters. If the message is too long to be displayed fully, some words from the end of the message should be cropped, keeping in mind that: the notification should be as long as possible; only whole words can be cropped; if any words are cropped, the notification should end with "…"; the dots should be separated from the last word by a single space; the notification may not exceed the K-character limit, including the dots. If all the words need to be cropped, the notification is "..." (three dots without a space). Functin Description: Complete function prepareNotification in the editor. Function prepareNotification has the following parameters: String message & int k Returns: The notification to display, which has no more than K chars, as described above.

Constraints

• K is an integer within the range [3..500]
• the length of string message is within the range [1..500]
• string message is made of English letters (a-z, 'A-Z) and spaces
• message does not contain spaces at the beginning or at the end
• words are separated by a single space (there are never two or more consecutive spaces)

Example 1

Input:

message = "And now here is my secret"
K = 15

Output:

"And now..."

Explanation: the notification "And ..." would be incorrect, because there is a longer correct notification the notification "And now her ..." would be incorrect, because the original message is cropped through the middle of a word the notification "And now ..." would be incorrect, because it ends with a space the notification "And now here..." would be incorrect, because it ends with a space the notification "And now here..." would be incorrect, because there is no space before the three dots the notification "And now here ..." would be incorrect, because it exceeds the 15-character limit The function should return "And now...", as explained above.

Example 2

Input:

message = "There is an animal with four legs"
K = 15

Output:

"There is an ..."

Explanation: The function should return "There is an...".

Example 3

Input:

message = "super dog"
K = 4

Output:

"..."

Explanation: The function should return "...".

Example 4

Input:

message = "how are you"
K = 20

Output:

"how are you"

Explanation: The function should return "how are you".

Given an array of size N, find the product of XOR of all good pairs in the array. A pair (A[i],A[j]) is called good only when 0 Input Format The first line of input contains T- number of test cases. The first line of each test case containsN- the size of the array. The second line of each test case contains theNelements. **Output Format** Print the product of XOR of all good pairs in the array. **Constraints** 30 points2 ≤ N ≤ 10³70 points2 ≤ N ≤ 10⁵General Constraints1 ≤ T ≤ 10 1 ≤ A[i] ≤ 3000`

Constraints

See above

Example 1

Input:

A = [1, 2, 3, 7]

Output:

720

Explanation: Example 1: (1²) * (1³) * (1⁷) * (2³) * (2⁷) * (3⁷) = 720

Example 2

Input:

A = [4, 3, 7]

Output:

84

Explanation: Example 2: (4³) * (4⁷) * (3⁷) = 84

Each business candidate is represented as [score, distance, isOpen], where isOpen is 1 for open and 0 for closed. Return the indices of the top k open businesses. Open businesses should be sorted by descending score. If two businesses have the same score, the one with the smaller distance comes first. If both score and distance are tied, keep the smaller original index first.

Constraints

Closed businesses must not appear in the result. If fewer than k businesses are open, return all open businesses in ranked order.

Example 1

Input:

candidates = [[90,4,1],[95,8,0],[90,2,1],[85,1,1]]
k = 2

Output:

[2,0]

Explanation: Candidate 1 is closed. Candidates 2 and 0 tie on score, so the smaller distance comes first.

Example 2

Input:

candidates = [[80,3,1],[80,2,1],[90,10,1]]
k = 5

Output:

[2,1,0]

Explanation: All open stores are returned because fewer than five stores are available.

There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, the Ministry of transport decided to orient the roads in one direction because they are too narrow. Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi. This year, there will be a big event in the capital (city 0), and many people want to travel to this city. Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed. It's guaranteed that each city can reach city 0 after reorder.

Constraints

• 2 ≤ n ≤ 5 * 10⁴
• connections.length == n - 1
• connections[i].length == 2
• 0 ≤ ai, bi ≤ n - 1
• ai ≠ bi

Example 1

Input:

n = 6
connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]

Output:

3

Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 2

Input:

n = 5
connections = [[1,0],[1,2],[3,2],[3,4]]

Output:

2

Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 3

Input:

n = 3
connections = [[1,0],[2,0]]

Output:

0

Explanation: No edges need to be changed, as each node can already reach the node 0.

Given an integer array nums and an integer k

Constraints

Assume 0 ≤ k ≤ nums.length. The return value should contain exactly k elements.

Example 1

Input:

nums = [5,1,3,5,2]
k = 3

Output:

[5,3,5]

Explanation: The three largest elements are 5, 5, and 3. They are returned in their original order.

Example 2

Input:

nums = [4,4,4,2]
k = 2

Output:

[4,4]

Explanation: When equal values cross the cutoff, keep the earliest occurrences needed to return exactly k elements.

Rever an integer (positive or negative) without turning the integer to a sring or using string manipulation Function Description Complete the function reverse in the editor. reverse has the following parameter:

• int x: the integer to reverse (˶˃⤙˂˶) Thanks a TON, Rachel

Constraints

• -2³¹ ≤ x ≤ 2³¹ - 1

Example 1

Input:

x = 123

Output:

321

Explanation: The reversed integer is 321. Since the reversed integer is within the signed 32-bit integer range, it is the return value.

Example 2

Input:

x = 120

Output:

21

Explanation: The reversed integer is 21. Notice that the leading zero in the input integer is not present in the reversed integer.

Example 3

Input:

x = -120

Output:

-21

Explanation: The reversed integer is -21. The negative sign is preserved during the reversal.

Strings with long blocks of repeating characters take much less space if kept in a compressed representation. To obtain the compressed representation, we replace each segment of equal characters in the string with the number of characters in the segment followed by the character (for example, we replace segment "CCCC" with "4C"). To avoid increasing the size, we leave the one-letter segments unchanged (the compressed representation of "BC" is the same string - "BC"). For example, the compressed representation of the string "ABBBCCDDDCCC" is "A3B2C2D3C", and the compressed representation of the string "AAAAAAAAAABXXAAAAAAAAAA" is "11AB2X10A". Observe that, in the second example, if we removed the "BXX" segment from the middle of the word, we would obtain a much shorter compressed representation - "21A". In order to take advantage of this observation, we decided to modify our compression algorithm. Now, before compression, we remove exactly K consecutive letters from the input string. We would like to know the shortest compressed form that we can generate this way. Given a string S of length N and an integer K, returns the shortest possible length of the compressed representation of S after removing exactly K consecutive characters from S.

Constraints

• N is an integer within the range [1..1,000,000];
• K is an integer within the range [0..100,000];
• K ≤ N;
• string S is made only of uppercase letters (A-Z).

Example 1

Input:

S = "ABBBCCDDCCC"
K = 3

Output:

5

Explanation: After removing "DDC" from S, we are left with "ABBBCCC", which compresses to a representation of length 5 - "A3B4C".

Example 2

Input:

S = "AAAAAAAAAABXXAAAAAAAAAA"
K = 3

Output:

3

Explanation: After removing "BXX" from S, we are left with "AAAAAAAAAAAAAAAAAAAAA", which compresses to a representation of length 3 - "21A".

Example 3

Input:

S = "ABCDDDEFG"
K = 2

Output:

6

Explanation: After removing "EF" from S, we are left with "ABCDDDG", which compresses to a representation of length 6 - "ABC3DG".

You have m square tiles of size 1 * 1 and n square tiles of size 2 * 2. Your task is to create the largest possible square using these tiles. Tiles may not overlap, and the resulting square should be filled (it should not contain empty spaces). Let's now write a func called sideLargetstSquare(int m, int n) in the editor Task of your func: Find the len of the side of the largest square you can create. If no square can be created, func should return 0.

Constraints

• 1 ≤ m, n ≤ 1,000,000,000

Example 1

Input:

m = 8
n = 0

Output:

2

Explanation: You can use four out of eight tiles to arrange them into 2 * 2 square. There are not enough tiles to create 3 * 3 square.

Example 2

Input:

m = 4
n = 3

Output:

4

Explanation: You can obtain 4 * 4 square by arranging four 1 * 1 tiles into a 2 * 2 square, and surrounding it by 2 * 2 tiles:

Example 3

Input:

m = 0
n = 18

Output:

8

Explanation: You need to use sixteen 2 * 2 tiles to create the square. Not that not all the tiles are used.

Example 4

Input:

m = 13
n = 3

Output:

5

Explanation: One of the possible arrangements is shown in the following image:

You are gien an array A of N integers, representing the maximum heights of N skyscrapers to be built. Your task if to specify the actual heights of the skyscrapers, given that: the height of the K-th skyscraper should be positive and not bigger than A[K] no two skyscrapers should be of the same height the toal sum of the skyscrapers' heights should be the maximum possible Given an array A of N integers, returns an array B of N integers where B[K] is the assigned height of the K-th skyscraper satisfying the above conditions. If there are several possible answers, the function may return any of them. You may assume that it is always possible to build all skyscrapers while fulfilling all the requirements.

Constraints

• N is an integer within the range [1..50,000]
• Each element of array A is an integer within the range [1..1,000,000,000]
• There is always a solution for the given input

Example 1

Input:

A = [1, 2, 3]

Output:

[1, 2, 3]

Explanation: As all of the skyscrapers may be built to their maximum height.

Example 2

Input:

A = [9, 4, 3, 7, 7]

Output:

[9, 4, 3, 7, 6]

Explanation: Note that [9, 4, 3, 6, 7] is also a valid answer. It is not possible for the last two skyscrapers to have the same height. The height of one of them should be 7 and the other should be 6.

Example 3

Input:

A = [2, 5, 4, 5, 5]

Output:

[1, 2, 3, 4, 5]

Explanation: N/A

A prefix of a string S is any leading contiguous part of S. For example, the string "codility" has the following prefixes: "", "c", "co", "cod", "codi", "codil", "codili", "codilit", and "codility". A prefix of S is called proper if it is shorter than S. A suffix of a string S is any trailing contiguous part of S. For example, the string "codility" has the following sufixes: "", "y", "ty", "ity", "lity", "ility", "dility", "odility" and "codility". A suffix of S is called proper if it is shorter than S. Let's now write a func called strWithLongestLen(String S) in the editor Task of your func: Find the len of the longest string that is both a proper suffix of S and a proper prefix of S. : 𓏲 ๋࣭ ࣪endless thanks, spike!˖࿐࿔

Constraints

• 1 ≤ S.length() ≤ 1,000,000
• String S consists only lower case english letters (a - z)

Example 1

Input:

S = "abbabba"

Output:

"4"

Explanation: Proper prefixes of S are: "", "a", "ab", "abb", "abba", "abbab", "abbabb" Proper suffixes of S are: "", "a", "ba", "bba", "abba", "babba", "bbabba" String "abba", with the longest len, is both a proper prefix and a proper sufix of S This is the longest such string.

Example 2

Input:

S = "codility"

Output:

"0"

Explanation: string "" is both a proper prefix and a proper suffix of S. This is the longest such string.

There is an array A of N integers and three tiles. Each tile can cover two neighbouring numbers from the array but cannot intersect with another tile. It also cannot be placed outside the array, even partially. Write a function: def solution(A) that, given an array A of N integers, returns the maximum sum of numbers that can be covered using at most three tiles.

Example 1

Input:

A = [2, 3, 5, 2, 3, 4, 6, 4, 1]

Output:

25

Explanation: There is only one optimal placement of tiles: (3, 5), (3, 4), (6, 4).

Example 2

Input:

A = [1, 5, 3, 2, 6, 6, 10, 4, 7, 2, 1]

Output:

35

Explanation: One of the three optimal placements of tiles is (5, 3), (6, 10), (4, 7).

Example 3

Input:

A = [1, 2, 3, 3, 2]

Output:

10

Explanation: There is one optimal placement of tiles: (2, 3), (3, 2). Only two tiles can be used because A is too small to contain another one.

Example 4

Input:

A = [5, 10, 3]

Output:

15

Explanation: Only one tile can be used.

You are provided with a map representing a connected country consisting of N cities. The cities are numbered from 1 to N and they are interconnected by N-1 edges, forming a tree-like structure. Each city's population possesses a unique measurement denoting their satisfaction level, represented by an array of length N. The satisfaction level of the city number i is given by the value A[i]. This country is governed by a peculiar king who takes a keen interest in conducting intriguing mathematical evaluations which sometimes appear nonsensical to assess the country's condition. His evaluation method is as follows:

• He calculates the sum of the satisfaction levels of the cities, which he denotes as the satisfaction level. In other words, he calculates the sum of the unique satisfaction level of the number of cities. Aware of numerous conflicts and political issues, the king recognizes the necessity of dividing his country into precisely two parts by removing a single edge. His objective is to identify the optimal edge that, when removed, would split the country into two parts, maximizing the sum of the king's evaluation for the two resulting countries. Find the maximum possible sum of satisfaction levels, representing the combined evaluations for the two resulting countries. Since the answer can be very large, return it modulo 10⁹+7. Input Format
• The first line contains an integer, N, denoting the number of cities in the country.
• The next line contains N integers, M, denoting the number of edges in the country.
• The next line contains an integer, M, denoting the number of cities in the country.
• Each line of the subsequent lines (where `0 ≤ i

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 10⁵
• 1 ≤ U, V ≤ N
• 1 ≤ A[i] ≤ 10⁹

Example 1

Input:

A = [1, 2, 3, 4, 5]
edges = [[1, 2], [1, 3], [3, 4], [3, 5]]

Output:

15

Explanation: For satisfaction levels, edge_removed=[(1,2), (1,3), (3,4), (3,5)], we get satisfaction=[(14,1), (12,3), (11,4), (11,4)]. In this case, the optimal solution is to cut the edge (1,3), which separates the tree into two trees [1,2] and [3,4,5]. The resulting trees have satisfaction levels of 3 and 12, respectively. Therefore, the best answer to evaluate is 3 + 12 = 15. Hence, the answer is 15.

Example 2

Input:

A = [1, 2, 2, 2, 2]
edges = [[1, 2], [1, 3], [3, 4], [3, 5]]

Output:

10

Explanation: For each edge cut of the tree to obtain "5 + 5 = 10" as the best answer. Hence, the answer is 10.

Example 3

Input:

A = [1, 2, 3, 1, 1, 1, 1]
edges = [[1, 2], [1, 3], [1, 4], [3, 5], [3, 6], [4, 7]]

Output:

9

Explanation: For each edge cut of the tree to obtain "6 + 3 = 9" as the best answer. In this case, the optimal solution is to cut the edge (1,3), which separates the tree into two trees [1,2,4,7] and [3,5,6]. The resulting trees have satisfaction levels of 6 and 3, respectively. Therefore, the best answer to evaluate is 6 + 3 = 9. Hence, the answer is 9.

We will call a sequence of integers a spike if they first increase (strictly) and then decrease (also strictly, including the last element of the increasing part). For example (4, 5, 7, 6, 3, 2) is a spike, but (1, 1, 5, 4, 3 and (1, 4, 3, 5) are not. Note that the increasing and decreasing parts always intersect, e.g.: for spike (3, 5, 2) sequence (3, 5) is an increasing part and sequence (5, 2) is a decreasing part, and for spike (2) sequence (2) is both an increasing and a descreasing part. You are given an array A of N integers. Your task is to calculate the length of the longest possible spike, which can be created from numbers from array A. Note that you are NOT supposed to find the longest spike as a sub-sequence of A, but rather choose some numbers from A and reorder them to create the longest spike. Given an array A of integers of length N, returns the length of the longest spike which can be created from the numbers from A. Desmond rocks!

Constraints

N/A

Example 1

Input:

A = [1, 2]

Output:

2

Explanation: As (1, 2) is already a spike :)

Example 2

Input:

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

Output:

6

Explanation: N/A T~T

Given an array and a range [lowVal, highVal], partition the array into three parts: All elements smaller than lowVal come first. All elements in the range [lowVal, highVal] come next. All elements greater than highVal come last. Additionally: If lowVal and highVal exist in the array, ensure that lowVal appears before highVal in the final result. The relative order of elements within each group doesn't matter. Function Description Complete the function threePartitionArray in the editor. threePartitionArray has the following parameters:

• int arr[]: an array of integers
• int lowVal: an integer representing the lower bound of the range
• int highVal: an integer representing the upper bound of the range halo frenz - you might want to checkout lc75. They said that these 2 questions are relevant :)

Constraints

nothin found againnnn 😭

You are given three integers N, M and K. An array is said to be good if there is exactly K indices i such that A[i] * A[i + 1] is equal to M. Find the number of good arrays A. Since the answer can be very large, return it modulo 10⁹ + 7. Input Format The first line contains an integer, N, denoting one of the given three integers. The next line contains an integer, M, denoting one of the three given integers. The next line contains an integer, K, denoting one of the three given integers.

Constraints

2 ≤ N ≤ 10⁹ 3 ≤ M ≤ 10⁹ 0 ≤ K ≤ min(50, N - 1)

Example 1

Input:

N = 2
M = 3
K = 0

Output:

7

Explanation: Given N = 2, M = 3, K = 0. There exists 7 possible arrays A. Some of them are [3, 3] and [1, 2].

Example 2

Input:

N = 2
M = 3
K = 1

Output:

2

Explanation: Given N = 2, M = 3, K = 1. There exists only two possible arrays A which are [1, 3] and [3, 1].

Example 3

Input:

N = 5
M = 10
K = 2

Output:

1368

Explanation: Given N = 5, M = 10, K = 2. There exists a total of 1368 possible arrays A.

You are given a string letters consisting of N English alphabet characters (a-z, A-Z). Your task is to determine how many distinct alphabet letters appear in both lowercase and uppercase, and all of the lowercase occurrences of that letter appear before any of its uppercase occurrences in the string. Function Signature Complete the function solution in the editor. solution has the following parameter:

• String letters: a string of English letters (a-z, A-Z) Input • A string letters of length N (1 ≤ N ≤ 100,000) • The string contains only English letters (a-z, A-Z) Output • Return an integer representing the number of distinct letters that satisfy the following:
• Both the lowercase and uppercase forms of the letter appear in the string
• All lowercase occurrences appear before any uppercase occurrence of that letter

Constraints

See above

• Round 1: Word Pattern II
• Round 2: Implement Queue using Stacks
• Round 3: Island Perimeter Given a pattern and a string s, return true if s matches the pattern. A string s matches a pattern if there is some bijective mapping of single characters to non-empty strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings. wallz carries!

Constraints

• 1 ≤ pattern.length, s.length ≤ 20
• pattern and s consist of only lowercase English letters.