Let's see how to check if all digits of $$$x$$$ are different. Since there can be only $$$10$$$ different numbers($$$0$$$ to $$$9$$$) in single digit, you can count the occurrences of $$$10$$$ numbers by looking all digits of $$$x$$$. You can count all digits by using modulo $$$10$$$ or changing whole number to string.

For example, if $$$x = 1217$$$, then occurrence of each number will be $$$[0, 2, 1, 0, 0, 0, 0, 1, 0, 0]$$$, because there are two $$$1$$$s, single $$$2$$$ and single $$$7$$$ in $$$x$$$. So $$$1217$$$ is invalid number.

Now do the same thing for all $$$x$$$ where $$$l \le x \le r$$$. If you find any valid number then print it. Otherwise print $$$-1$$$.

Time complexity is $$$O((r-l) \log r)$$$.

# Return if given number's digits are distinct.
def is_distinct(x):
    return len(set(str(x))) == len(str(x))

L, R = map(int, input().split())

found = False
for i in range(L, R+1):
    if is_distinct(i):
        found = True
        print(i)
        break
    
if not found:
    print(-1)

If s is palindromic initially, we can operate on the interval [1,n], the answer is $$$Yes$$$.

Let's consider the other case. In a palindrome s, for each $$$i$$$ in $$$[1,⌊n/2⌋]$$$, $$$s_i=s_{n−i+1}$$$ must hold. For those $$$i$$$, we may check whether $$$s_i=s_{n−i+1}$$$ is true in the initial string. For all the illegal positions $$$i$$$, the operation must contain either $$$i$$$ or $$$n+1−i$$$, but not both. For the legal positions, the operation must contain neither of $$$i$$$ nor $$$n+1−i$$$, or both of them.

If the illegal positions is continuous (which means that they are $$$l,l+1,…,r−1,r$$$ for some $$$l$$$ and $$$r$$$), we may operate on the interval $$$[l,r]$$$ (or $$$[n+1−r,n+1−l]$$$), making the string palindromic. The answer is $$$Yes$$$.

Otherwise, there must be some legal positions that lie between the illegal ones. Suppose the illegal positions range between $$$[l,r]$$$ (but not continuous). This interval covers all the legal positions that lie between the illegal ones but does not cover their symmetrical positions. Thus, such kind of operation will produce new illegal positions. In other words, there are no valid operations in this situation. The answer is $$$No$$$.

Total complexity: $$$O(n)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    found = False
    last = None
    ans = "Yes"
    for i in range(n // 2):
        if s[i] != s[n - 1 - i]:
            if not found:
                found = True
            else:
                if i - 1 != last:
                    ans = "No"
                    break
            last = i
            
    print(ans)

Lets look at the optimal answer. It will contain several segment of increasing beauty and between them there will be drops in the beautifulness.to determine number of such segments. From the way we construct answer it is easy to see that the number of segments always equal to the maximal number of copies of one value. Obviously we can't get less segments than that and our algorithm gives us exactly this number. Total complexity: $$$O(n)$$$

from collections import Counter
n = int(input())
nums = list(map(int, input().split()))
count = Counter(nums)
ans = 0
while len(count) > 0:
    ans += (len(count) - 1)
    keys = list(count.keys())
    for key in keys:
        count[key] -= 1
        if count[key] == 0:
            del count[key]
print(ans)

In this problem the sensible thing to do is to count the amount of times we are going to add some index of this sequence; then the maximal number gets assigned to the index that is added the most, and so on. In order to count the amount of times we referenced each index, we can use normal line sweep to store cumulative sums. Finally sort both arrays (the prefix sum array and the main array) and sum the product of the elements on the same index from both arrays.

Time complexity: $$$\mathcal{O}(nlogn)$$$.

Memory complexity: $$$\mathcal{O}(n)$$$.

from itertools import accumulate
from sys import stdin


def input(): return stdin.readline()


N, Q = map(int, input().split())
nums = sorted(map(int, input().split()))

line = [0]*(N + 1)
for _ in range(Q):
    l, r = map(int, input().split())
    line[l - 1] += 1
    line[r] -= 1

counts = sorted(accumulate(line[:-1]))

ans = 0
for i in range(N):
    ans += counts[i]*nums[i]

print(ans)

What can we say about the position of the maximum elements relative to $$$[l,r]$$$?

Iterate over the middle maximum element and choose $$$[l,r]$$$ greedily.

First we need to notice, that two of the maximums are at the ends of $$$[l,r]$$$, otherwise we can move one of the boundaries closer to the other and improve the answer.

Using this observation we can reduce the problem to the following: choose three indices $$$l<m<r$$$, such that $$$b_l+b_m+b_r−(r−l)$$$ is maximum.

Now, let's iterate over the middle index $$$m$$$ and rewrite the function as $$$b_m+(b_l+l)+(b_r−r)$$$. We can see, that values in the braces are pretty much independent — on of them depends only on the index $$$l$$$ and the second one depends only on the index $$$r$$$ . So, for a given $$$m$$$ we can choose the numbers $$$l$$$ and $$$r$$$ greedily! To make it fast enough we can pre calculate the prefix maximum for the array $$$b_l+l$$$ and the suffix maximum for array $$$b_r−r$$$.

Total complexity: $$$O(n)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    prefix = []
    suffix = []
    for i in range(n):
        prefix.append(nums[i] + i)
        suffix.append(nums[i] - i)
    for i in range(1, n):
        prefix[i] = max(prefix[i], prefix[i - 1])
        suffix[n - i - 1] = max(suffix[n - i - 1], suffix[n - i])
    ans = float("-inf")
    for i in range(1, n - 1):
        ans  = max(ans, prefix[i - 1] + nums[i] + suffix[i + 1])
    print(ans)