Split the input into three strings, take the first character of each, and join them.

for _ in range(int(input())):
  print(''.join(x[0] for x in input().split()))

We use a stack to keep track of characters. For each character, if it matches the top of the stack, we remove the top (both letters cancel out). Otherwise, we push the current character onto the stack. At the end, the stack contains the corrected string without consecutive duplicates.

python s=input() st=[] for c in s: if st and st[-1]==c: st.pop() else: st.append(c) print(''.join(st))

To solve this problem, we simulate the bombing process using a stack. We process each character of the string from left to right. If the current character is 'B' and the top of the stack is either 'A' or 'B', it means we have found a bombable substring ("AB" or "BB"), so we remove the top character from the stack (this simulates bombing and removing the substring). If not, we simply push the current character onto the stack. After processing the entire string, the stack will contain the characters that could not be bombed. Therefore, the length of the stack gives the length of the shortest string that BoomBoom can make. This approach is efficient, working in linear time relative to the size of the string.

t = int(input())
for _ in range(t):
    s = input()
    st = []
    for c in s:
        if c == 'B' and st and st[-1] in 'AB':
            st.pop()
        else:
            st.append(c)
    print(len(st))

The problem involves determining whether two wires ("plus" and "minus") can be untangled based on a sequence of their relative positions. The sequence consists of + and -, where + means the "plus" wire is above the "minus" wire, and — means the "minus" wire is above the "plus" wire. The goal is to check if the sequence of these crossings can be resolved by simple operations such as moving the wires over each other. The approach simulates this by using a stack-like structure to keep track of the wire crossings. Every time the wires cross in an alternating manner (e.g., a + followed by a -), we add it to the stack. If the same crossing repeats (like two +s or two -s consecutively), we pop the last element from the stack, essentially removing the crossed wires and simulating the untangling.

The key idea behind this solution is that each crossing that needs to be removed forms a pair (either ++ or --). Thus, we can think of this as matching pairs of crossings. As we traverse the sequence, if we encounter a character that matches the last one in the stack, we remove the last one. This operation models the untangling process, where crossing wires cancel each other. After processing the entire sequence, if the stack is empty, it indicates that all crossings have been untangled, and the answer is "Yes." Otherwise, if there are remaining elements in the stack, it means the wires are still tangled, and the answer is "No."

wire = input()
result = []

for val in wire:
    if not result:
        result.append(val)
        continue
    if result[-1] != val:
        result.append(val)
    else:
        while result and val == result[-1]:
            result.pop()

if result:
    print('No')
else:
    print('Yes')

The problem requires constructing a lexicographically minimal string from a given input string s by using a stack-based approach. The strategy is to use a stack to store characters while ensuring that the result string remains in the smallest possible lexicographical order. The core idea is to push characters from s into the stack, and at each step, we check if the current character at the top of the stack should be popped to form the smallest possible result.

To achieve this, we first preprocess the string s to count the occurrences of each character. Then, for each character in s, we append it to the stack and decrease its count. After that, we check if the character at the top of the stack can be removed by checking whether any smaller character still exists in the remainder of the string. If a smaller character exists, we stop popping and move to the next character.

The algorithm ensures that the string u formed by popping characters from the stack is lexicographically minimal. The key condition is that we always push a character to the stack but only pop it if no smaller character is remaining further down the string.

The time complexity of this approach is O(n), where n is the length of the string s. Each character is pushed and popped from the stack at most once. The inner loop for checking smaller characters runs in constant time because we only check the count array, which has a fixed size of 26. Therefore, the overall time complexity is linear with respect to the length of the input string.

s = input()
count = [0] * 26
for c in s:
    count[ord(c) - ord('a')] += 1

stack = []
answer = []

for c in s:
    idx = ord(c) - ord('a')
    stack.append(c)
    count[idx] -= 1

    while stack:
        top = stack[-1]
        top_idx = ord(top) - ord('a')

        if any(count[i] > 0 for i in range(top_idx)):
            break
        answer.append(stack.pop())

print(''.join(answer))

Think of the operations in reverse order instead of forward.

Track a balance at each step. balance = push count − pop count

We solve the problem by reversing the way we think about stack operations. Instead of applying operations in their original order, we reverse them. In this reversed sequence, the top of the stack after any number of operations will correspond to the first push(x) operation whose contribution has not been canceled out by earlier pop() operations. To track this efficiently, we define a quantity called balance at each operation position. Formally, balance[i] = (number of push operations up to i) − (number of pop operations up to i). When a push(x) occurs, the balance increases by +1; when a pop() occurs, the balance decreases by -1. Therefore, at any moment, the element at the top of the stack corresponds to the first operation where the balance becomes positive.

To manage this efficiently, we use a structured approach to track balances quickly. Instead of calling it a complicated "segment tree," we think of it as a balance tracking tree. In this tree, we maintain two things: max_balances[i], which keeps the maximum balance in the subtree rooted at node i, and total_balances[i], which keeps the total balance sum in that subtree. When a new operation at position p is remembered, if it is a push(x), we set the balance at that position to +1; if it is a pop(), we set the balance to -1. Then, we propagate this change upwards through the tree to keep all balances and maximum values correct.

Once balances are updated, to find the current top of the stack, we start from the root of the tree and always prioritize moving toward the right child if it has a positive maximum balance. If not, we adjust our offset (running sum) by adding the total balance of the right child and move to the left child. This way, once we reach a leaf node, we directly find the operation that corresponds to the top value on the stack. This traversal guarantees that we always find the first push(x) that has not been canceled by enough pop() operations.

The efficiency of this method comes from the fact that each update or query takes only O(log m) time, where m is the number of operations. Since Malak remembers each of the m operations one by one, the total time complexity is O(m log m), which is perfectly acceptable even for large m (up to 10⁵). Thus, the approach is both intuitive when thought of as balancing pushes and pops and highly efficient thanks to the structure used for tracking.

m = int(input())
N = 1
while N < m:
    N *= 2

max_balances = [0] * (2 * N)
total_balances = [0] * (2 * N)
values = [0] * m

for _ in range(m):
    parts = input().split()
    p = int(parts[0])
    t = int(parts[1])

    if t == 0:
        max_balances[N + p - 1] = 0
        total_balances[N + p - 1] = -1
    else:
        x = int(parts[2])
        values[p - 1] = x
        max_balances[N + p - 1] = 1
        total_balances[N + p - 1] = 1

    j = (N + p - 1) // 2
    while j >= 1:
        total_balances[j] = total_balances[2 * j] + total_balances[2 * j + 1]
        max_balances[j] = max(
            max_balances[2 * j + 1],
            max_balances[2 * j] + total_balances[2 * j + 1],
            0
        )
        j //= 2

    if max_balances[1] == 0:
        print(-1)
        continue

    j = 1
    offset = 0
    while j < N:
        if max_balances[2 * j + 1] + offset > 0:
            j = 2 * j + 1
        else:
            offset += total_balances[2 * j + 1]
            j = 2 * j

    print(values[j - N])