# STRQRYCF - Editorial

Author, Tester & Editorialist: Hritik Seth

EASY - MEDIUM

Strings, Hashing

# PROBLEM:

Mr. Seth loves to play with strings, so he provides you a string S of lowercase alphabets and a positive integer Q.

You have to process Q queries of following two types:

• 1 L X - change the character at index L to X. (1-based indexing)
• 2 K - print the K^{th} largest frequency character in string S, if it exists otherwise print -1.

Note: If there exists multiple K^{th} largest frequency characters then print the lexicographically smallest one.

# EXPLANATION:

• Brute Force approach would be, iterate over every character in the string and store it’s frequency and then sort the frequency array to find the K^{th} largest if exists. To update the character at any index also you will need to iterate over string.

This approach would take overall Time Complexity of O(q*n^3) and works for subtask 1.

• Optimised Approach would be to create a hash of characters to store frequency (only takes O(26) extra space) and then find the distinct frequencies for K^{th} largest frequency if it exists. In this approach updation will take constant time.

This approach would take overall Time Complexity of O(n + q) and works for all subtasks.

Note - Sorting and extra operations would take O(26*log26) time. So we considered it as constant.

# SOLUTIONS:

Editorialist's Solution
``````for _ in range(int(input())):
n, queries = map(int, input().split())
string = input()
characters = []
frequency =  * 26
for i in string:
# storing the characters for query 1 operations
characters.append(i)
# calculating frequency of character with 0-th index as 'a', 1-st as 'b' and so on...
frequency[ord(i) - 97] += 1
for i in range(queries):
l = list(map(str, input().split()))
# checking for query type
if l == '2':
k = int(l)
distinct_fequency = set()
for j in frequency:
if(j != 0 and j not in distinct_fequency):
# adding different frequency elements to set
# distinct frequencies < k
if(k > len(distinct_fequency)):
print(-1)
else:
distinct_fequency = list(distinct_fequency)
# sort in reverse order to find k-th largest frequency
distinct_fequency.sort(reverse=True)
# now the frequency which is the k-th largest will match with the first occurence in frequency list (lexicographically smallest)
print(chr(frequency.index(distinct_fequency[k - 1]) + 97))
else:
x, c = int(l), l
# we decrease the frequency of the old character
frequency[ord(characters[x - 1]) - 97] -= 1
# we increase the frequency of the replacing character
frequency[ord(c) - 97] += 1
# replace the character in the string
characters[x - 1] = c
``````

Well this was my approach, feel free to share your approach here. Suggestions are always welcomed.

1 Like