Google Kickstart Round A 2021: K-Goodness String
Google Kickstart Round A 2021 Solution to K-Goodness String problem explained in detail in Python with Time and Space Complexities.
In this post, we’ll be looking at one of the easiest problems of Google Kickstart Round A 2021, that is, K-Goodness String. So without further ado, let’s begin!
Problem
Charles defines the goodness score of a string as the number of indices i such that Si≠SN−i+1 where 1≤i≤N/2 (1-indexed). For example, the string CABABC has a goodness score of 2 since S2≠S5 and S3≠S4.
Charles gave Ada a string S of length N, consisting of uppercase letters and asked her to convert it into a string with a goodness score of K. In one operation, Ada can change any character in the string to any uppercase letter. Could you help Ada find the minimum number of operations required to transform the given string into a string with goodness score equal to K?
Input
The first line of the input gives the number of test cases, T. T test cases follow.
The first line of each test case contains two integers N and K. The second line of each test case contains a string S of length N, consisting of uppercase letters.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of operations required to transform the given string S into a string with goodness score equal to K.
Limits
Memory limit: 1 GB.
1≤T≤1001≤T≤100.
0≤K≤N/20≤K≤N/2.
Test Set 1
Time limit: 20 seconds.
1≤N≤1001≤N≤100.
Test Set 2
Time limit: 40 seconds.
1≤N≤2×1051≤N≤2×105 for at most 1010 test cases.
For the remaining cases, 1≤N≤1001≤N≤100.
Sample
| Sample Input | Sample Output |
| 2 5 1 ABCAA 4 2 ABAA | Case #1: 0 Case #2: 1 |
Solution:-
First we need to calculate the goodness score, that is, the number of unmatched pairs in the given string. Pairs here are composed of the characters at ith and (n-i-1)th indices of the string S.
Then our result simply becomes the absolute difference between the target score K and the current goodness score. Have a look at the solution given below –
Time Complexity: O(N)
As we are traversing over the string S just once, the time complexity comes out to be O(N).
Space Complexity: O(1)
If we disregard the input space, we are not consuming any extra space resulting in a constant space complexity O(1).
