STRQRYCF - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author, Tester & Editorialist: Hritik Seth

DIFFICULTY:

EASY - MEDIUM

PREREQUISITES:

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 = [0] * 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[0] == '2':    
            k = int(l[1])
            distinct_fequency = set()
            for j in frequency:
                if(j != 0 and j not in distinct_fequency):
                    # adding different frequency elements to set
                    distinct_fequency.add(j)    
            # 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[1]), l[2]
            # 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