• What would you do if the constraints for the coordinates were up to (10^5)?

• You could use the line sweep algorithm, but the coordinates go up to (10^9). So, what shall we do?

• What if you use a dictionary instead of an array to store only the relevant positions?

We perform a line sweep using a dictionary to record events at positions where the number of covering segments changes. Sorting the dictionary keys lets us compute the prefix sum between these "critical" points. For each interval ([prev, cur)), the number of integer points is ((cur — prev)) and they are all covered by the current number of segments. This way, we aggregate the answer for every (k) in ([1, n]) without iterating over every integer in a huge range.

import sys
from collections import defaultdict

n = int(sys.stdin.readline().strip())
events = defaultdict(int)

# Record events: +1 when a segment starts, -1 when it ends (at r+1)
for _ in range(n):
    l, r = map(int, sys.stdin.readline().split())
    events[l] += 1
    events[r + 1] -= 1

# Sort the event points
keys = sorted(events.keys())
coverage = 0
prev = keys[0]
result = defaultdict(int)

# Line sweep: update coverage and count points in intervals
for point in keys:
    result[coverage] += point - prev
    coverage += events[point]
    prev = point

# Output counts for points covered by exactly 1 to n segments
ans = [result[k] for k in range(1, n + 1)]
print(*ans)
    

Let's consider a very special case of equal distances. What if all distances were equal to $$$1$$$? It implies that if some letter appears exactly twice, both occurrences are placed right next to each other.

That construction can be achieved if you sort the string, for example: first right down all letters '$$$a$$$', then all letters '$$$b$$$' and so on. If a letter appears multiple times, all its occurrences will be next to each other, just as we wanted.

Overall complexity: $$$O(|s|log|s|)$$$ or $$$O(|s|)$$$ per testcase.

for _ in range(int(input())):
  print(''.join(sorted(input())))