Two pointers: 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.

Time: O(N)

for _ in range(int(input())):
    n, s = int(input()), input()
    l, r = 0, n - 1
    while l < r:
        if s[l] == s[r]:
            break 
        l += 1
        r -= 1
    print(r - l + 1)

Sorting & Two pointers: There are different ways to solve this problem. But let's stick with the simplest one for now. Let's simplify the question by restating it as how many boys can be paired with girls at maximum. The first thing that might come to your mind is process the boys one by one and try to pair them with one girl if there is a match. That looks good. Let's try it.

Eg. Let a = [2, 3] and b = [2, 1]. Now let's pair the first boy 2 with the first girl 2. Next when we try to pair the second boy 3 with the second girl 1, we notice that abs(3 - 1) > 1 and we return [(2, 2)] as our end result. There is one problem though. We could pair them as [(2, 1), (3, 2)] and could've gotten more pairs. Hmm... Is our approach wrong? Yes. But with slight improvement (__Sorting__), we can make it right. What is the problem in our previous approach? Matching in a non-optimal way. So to fix this issue, sort the boys and pick a pair for the boys (if there is a match) one by one. One constraint would be to pick the smallest value from the perfectly matched girls, leaving more options for later boys. Intuition: Boys with large values need girls with large values and boys with small values need girls with small values.

Time: O(NlogN + MlogM)

n, a = int(input()), sorted(map(int, input().split()))
m, b = int(input()), sorted(map(int, input().split()))

pairs = i = j = 0
while i < n and j < m:
    if abs(a[i] - b[j]) < 2:
        pairs += 1
        i += 1
        j += 1
    elif a[i] < b[j]:
        i += 1
    else:
        j += 1

print(pairs)

Time: O(NlogN + M)

from collections import Counter

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

a.sort()

count = Counter(b)

pairs = 0
for x in a:
    if count[x - 1]:
        count[x - 1] -= 1
        pairs += 1
    elif count[x]:
        count[x] -= 1
        pairs += 1
    elif count[x + 1]:
        count[x + 1] -= 1
        pairs += 1

print(pairs)

Sorting & Two pointers: Straightforward implementation would be enough. Sort the input so that you can make close elements adjacent to each other. For each index increase the index as long as the difference between the next index's value and the current index's value is not more than one.

Time: O(NlogN)

pages = sorted(list(map(int, input().split(','))))

n = len(pages)

i, res = 0, []

while i < n:

    j = i + 1
    while j < n and pages[j - 1] + 1 >= pages[j]:
        j += 1

    if pages[i] == pages[j - 1]:
        res.append(f"{pages[i]}")
    else:
        res.append(f"{pages[i]}-{pages[j - 1]}")

    i = j 

print(','.join(res))

Sorting: We are ordered to buy n items in total and at least k items now (with the current week's market price). Our goal is to maximize profit. Therefore, we try to buy items that gives us high profit. Which ones? Let's see with an example.

Eg. Let k = 1, a = [2, 2] and b = [4, 10]. We have three options.
1. Buy the first item this week and the second item next week. Total price = 2 + 10 = 12
2. Buy the second item this week and the first item next week. Total price = 4 + 2 = 6
3. Buy both items this week. Total price = 2 + 2 = 4

Q:
- Why is the second option better than the first one? Because we bought an item whose price has increased by much during the next week. The first option buys the item whose price didn't increase by much and puts the other for next week. But the second option wisely chooses the item whose value increased by much (because it would've cost more if it would've been put for next week) and puts the ones that didn't change by much for next week. Conclusion: Always prefer the item whose price increased by much over the ones that changed by smaller value.

- Why is the third option better than the second one? Because the third option buys extra items even after all k items bought. Conclusion: If there are still some items left that are not bought but could give profit buy them.

To solve this problem we need at first to sort all items in increasing order of values a[i] - b[i]. Then let's iterate through sorted array. If for the current item x we did not buy k items now and if after discounts it will cost not more than now, we need to buy it now and pay a[x], in the other case we need to buy item x after discounts and pay b[x].

Time: O(NlogN)

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

c = sorted(range(n), key=lambda i: a[i] - b[i])

res = 0
for i in range(n + 1):
    if i >= k and (i == n or a[c[i]] - b[c[i]] > 0):
        break 
    res += a[c[i]]

for j in range(i, n):
    res += b[c[j]]

print(res)

This one is implementation problem. Let's break down the algorithm and implement it step by step.

Step 1: Move elements from array A to array B. In this step, have a left_arr and right_arr, and then insert elements of A one by one, alternating between the two sub-arrays. You don't have to worry when the total length is even. After this step, we have moved all elements from array A to array left_arr and right_arr. Array A is now empty, and array B(left_arr + right_arr) has n elements.

Step 2: Move elements from array B(which is left_arr + right_arr) to array C. In this step, we merge the two sub-arrays left_arr and right_arr to form the final array C . The merging is done by taking the the smaller element from the top of the left_arr vs right_arr if they have equal size if not we take element from the array with larger size

Finally check if the final c is sorted by c == list(sorted(x)).