Given a String of Buckets (alphabets). Find the cost (possibly minimal) to bring all the buckets at-CodePudding

Bob is a construction worker who does mathematics for increasing his efficiency. He is working on a site and has n buckets of cement-lined up with different characters (a – z) marked upon them. He has a strict command from the senior that he cannot change the order of the buckets.

Before starting his work, he has been given a string s of length n in which the character at position i (1 <= i <= n) gives us the mark on the i'th bucket. He can only carry one bucket at a time and bring it back to the base site. In each round, he has a criterion on which bucket to pick up. He will take the bucket with the smallest character marked upon it (a<b<z) and if there are multiple buckets with the smallest character, then he will take the one closest to the base. The cost of picking up a bucket B is the number of buckets he passes through while walking from the site to get B (the bucket which he picks is also included). In each round, the cost accumulates. Find the final cost incurred by Bob while completing his job.

Constraints

1 < t,m < 10^5

The sum of n over all test cases does not exceed 10^6

SAMPLE INPUT

2
badce

SAMPLE OUTPUT

Explanation

badce - Firstly Bob takes the second basket with mark 'a' and adds 2 to the cost.
bdce - Then he takes the first basket with the mark 'b' and adds 1 to the cost.
dce - Then he takes the second basket with the mark 'c' and adds 2 to the cost.
de - Again he takes the first basket with the mark 'd' and adds 1 to the cost.
e - Again he takes the first basket with the mark 'e' and adds 1 to the cost.

The total cost becomes 7 units.

I have tried to code in Python but giving TLE for some cases. Here is my approach-->

n = int(input())
s = input()
count_array = [0] * 26
for i in range(n):
    count_array[ord(s[i])-97]  = 1

alphabets = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
    
ans = 0

for i in range(26):
    while count_array[i] > 0:
       idx = s.index(alphabets[i])
       ans  = idx   1
       if idx > -1: s = s[0:idx]   s[idx 1:]
       count_array[i] -= 1
    
print(ans)

I am looking for an optimized approach that takes O(nlogn) or O(n) time complexity. Thank You.

CodePudding user response：

This runs in O(n). For every char, check how many previous chars will be transported later.

def get_cost(s):
    result = 0
    seen = [0] * 26
    for c in s:
        idx = ord(c) - ord('a')
        result  = 1   sum(seen[idx 1:])
        seen[idx]  = 1
    return result