Xenia wants to compute the total of integer summands, but she can only do it if the summands are sorted in a non-decreasing manner, therefore we may assist her as follows:

• step 1: remove the “+” character from the given string.
• Step 2: sort the summands in an increasing order.
• Step 3: replace the “+” character between the summands.

input = input().split("+")
input.sort()
li = []
for i in range(len(input)):
   li.append(input[i])
   if i < len(input) - 1:
       li.append("+")
 
string = "".join(li)
print(string)

Time complexity: $$$O(nlogn)$$$ Space complexity: $$$O(n)$$$

The straight forward solution to this problem is simulating the process. This can be achieved by pooping the elements from the two ends of using Two pointers. And counting the score point gained by the two players.

n = int(input())
nums = list(map(int,input().split()))

l,r = 0,len(nums)-1
i = 0
sereja = dima = 0
while l<=r:
    if i % 2 == 0:
        if nums[l] > nums[r]:
            sereja += nums[l]
            l += 1
        else:
            sereja += nums[r]
            r -= 1
    else:
        if nums[l] > nums[r]:
            dima += nums[l]
            l += 1
        else:
            dima += nums[r]
            r -= 1
    i += 1
    
print(sereja,dima)

Time Complexity: $$$O(n)$$$ Space Complexity: $$$O(1)$$$ where $$$n$$$ is number of cards

Understanding the problem:

1. There is a frog and it can jump in both directions(left or right) from some index.
2. The frog can jump to Left direction if s[i] = 'L' and it can jump to Right direction if s[i] = 'R', for i [0, n-1] where n is the length of the string.
3. It can only jump upto the boundary of the array. It cannot go past 0 index in the left direction and it cannot go past n-1(where n is length of string). let, d be the distance you decided to use to jump.
4. From the first index (0), you can only go to right, 'R'
5. What is the minimum d you have to use to get from 0 to n-1? d is the maximum jump you have done anywhere in the string. And, you want to minimize d.

Insight:

1. we should ignore 'L' because it will just take us backward.
2. we should only keep track of the maximum distance between two 'R'
3. for example, RLLLRLR, it takes 4 distances to jump from 0 to 4 index. and it takes 2 distances to jump from 4 to 6. And, the maximum distance we have used so far is 4. So, the answer will be 4.

Psuedo code:

set starting index to -1
set max_distance to 0
append 'R' at the end of the string
iterate through the string from i = 0..n
    if string[i] == "R":
       update max distance with max(max_distance, i - starting_index)
       set starting index to i
return max_distance

n = int(input())

while n>0:
    li = list(input())
    li.append("R")
    max_distance = 0
    s = -1
    for i in range(len(li)):
        if li[i] == "R":
            max_distance = max(max_distance, i-s)
            s = i
    n-=1
    print(max_distance)

Complexity analysis

Time complexity is $$$O(n)$$$ because we are iterating over the string once Space complexity is $$$O(1)$$$ because we are not using any auxiliary data structure

The solution is trivial for a single player having maximum score. But it needs more work if we have two or more players with a maximum score. The rule says If two or more players have a maximum score, m at the end of the game we have to look for a player that scored at least m points first in some round, and that player becomes the winner of the game.

let’s say the players are Mike and John, their score in each round is given in the following manner:

Mike 20 John 10 Mike -10

at the end of the game both of the players will have a maximum score, m=10. In order to find the winner we have to look for the player who scored at least m points first. We can see that Mike scored 20 before John scored 10, thus making Mike the winner of the game.

Algorithm

Data Structure we will use:

A dictionary called score to keep track of the scores each player have.

A set called winners to store the candidate winners

A list called history to store the inputs we are given in each round. This comes in handy when we have more than one candidate winners, then we have to play the game again (traversing the history array) to find the player in the winners set who scored at least m points first, m being the maximum score at the end of the game.

The steps are as follows:

1. we update the score of player’s in each round
2. we traverse through the scores of the players to find the maximum score, m.
3. we separate players with score m into winners set
4. we traverse through the history array to find the first person to score at least m points first.
5. Check if the first person to score m point first is in the winners set since players that are not winner candidate may score m points first

score = {}
history = []
winners = set()
 
n = int(input())
 
for i in range(n):
    s = input()
    history.append(s)
    name,val = s.split()
    val = int(val)
    score[name] = score.get(name,0) + val
    
maxScore = max(val for name,val in score.items())
 
for name,val in score.items():
    if val == maxScore:
        winners.add(name)
 
roundScore = {}
for i in range(len(history)):
    name,score = history[i].split()
    score = int(score)
    roundScore[name] = roundScore.get(name,0) + score
    
    if roundScore[name]>=maxScore and name in winners:
        print(name)
        break

Time complexity: $$$O(n)$$$, $$$n$$$ is number of rounds Space Complexity: $$$O(n)$$$, the history array is a size of $$$n$$$