Problem Link
Author: Divesh
Testers: Ankit, Bhuvnesh Jain, Priyank and Vibhav
Editorialist: Bhuvnesh Jain
Difficulty
EASY
Prerequisites
Greedy Techniques, Greatest common divisor.
Problem
You are given a string and a number K. You need to replace some characters with their corresponding values (given in the problem). For all possible changes in the string, find the maximum cost of any string where the cost is given by
count of letters - count of numbers + (sum of numbers/K)
Explanation
Let us first modify the function to just contain terms related to numbers only. For this, we use the below observation, at any given instant,
count of letters + count of numbers = N (length of string)Thus the cost now becomes:
N (length of string) - 2 * count of numbers + (sum of numbers/K)IN the above formula, N is constant and other things are variable based on the number of operations we chose to perform. If we try to replace a character by its corresponding number, then count increase by 1 and sum increase by its value. This means cost decreases by 2 and increases by (value/k). So applying a greedy approach by replacing only those characters with numbers whose values are greater than 2 * k, we can attain maximum cost of any possible replacements in the string.
The last thing was to correctly compute this cost in the string in the format specified by the problem. For this, we first compute the numerator and denominator of the fraction obtained. In case, their gcd is not 1, we divide each of them by their gcd so that they are in reduced form.
For details, refer to the tester’s solution below.
Time Complexity
O(N), per test case.
Space Complexity
O(N) per test case.
