We can easily calculate the sum of money that we need to buy all the bananas that we want, let's name it req.

If n >= req the answer is 0, because we don't need to borrow anything.

Otherwise the answer is req - n.

k, n, w = map(int, input().split())
tot = (w * (w + 1)) // 2
req = tot * k
print(max(req - n, 0))

Let's perform the process in reverse: we will remove the first and last character of the string, if these two characters are different. We should do this as long as possible, since we need to find the shortest initial string.

So the algorithm is straightforward: keep track of the left and right characters, and if they are different, remove both. Otherwise, output the length of the current string (or output 0 if the string became empty).

There are a few ways to implement this. For example, you can keep two pointers, one at the beginning of the string and one at the end, say, l=1 and r=n, and check if $$$s_l$$$=$$$s_r$$$. If it's true, then we increment l and decrement r. Otherwise, we output r−l+1. We stop when l≥r.

The time complexity is O(n).

def solve():
    n = int(input())
    s = input().strip()
    l, r, ans = 0, n - 1, n
    while s[l] != s[r] and ans > 0:
        l += 1
        r -= 1
        ans -= 2
    print(ans)

def main():
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

Let's sort boys and girls by skill. If boy with lowest skill can be matched, it is good idea to match him. It can't reduce answer size. Use girl with lowest skill to match.

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()

    m = int(input())
    b = list(map(int, input().split()))
    b.sort()

    boy, girl = 0, 0
    ans = 0
    while boy < n and girl < m:
        diff = abs(a[boy] - b[girl])
        if diff <= 1:
            boy += 1
            girl += 1
            ans += 1
        elif a[boy] < b[girl]:
            boy += 1
        else:
            girl += 1

    print(ans)

if __name__ == "__main__":
    main()

At first we sort all friends in money ascending order. Now the answer is some array subsegment. Next, we use the method of two pointers for finding the required subsegment.

Time complexity — O(n log n).

def main():
    n, d = map(int, input().split())
    v = []
    for i in range(n):
        a, b = map(int, input().split())
        v.append((a, b))
    v.sort()
    sum_val = 0
    ans = 0
    j = 0
    for i in range(n):
        sum_val += v[i][1]
        while j <= i and v[j][0] + d <= v[i][0]:
            sum_val -= v[j][1]
            j += 1
        ans = max(ans, sum_val)
    print(ans)

if __name__ == "__main__":
    main()