Round A 2021 Google Kick Start K-Goodness String problem | JAVA | Know About

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≤100.
0≤K≤N/2.

Test Set 1

Time limit: 20 seconds.
1≤N≤100.

Test Set 2

Time limit: 40 seconds.
1≤N≤2×105 for at most 10 test cases.
For the remaining cases, 1≤N≤100.
Sample

In Sample Case #1, the given string already has a goodness score of 1. Therefore the minimum number of operations required is 0.

In Sample Case #2, one option is to change the character at index 1 to B in order to have a goodness score of 2. Therefore, the minimum number of operations required is 1.

In sample case #2, there are no 2-countdowns.

In sample case #3, there is one 6-countdown as highlighted below.

100 7 6 5 4 3 2 1 100



PSEUDOCODE


int kGoodnessString(string s, int k) { int minOperations = 0, x = 0; for(int i = 0; i < s.size() / 2; i++) { if(s[i] != s[s.size() - i - 1]) { x++; } } if(x == k) { minOperations = 0; } else if(x > k) { minOperations = x - k; } else { minOperations = k - x; } return minOperations;

Solution


import java.io.*; import java.util.*; public class Solution { public static int n = (int) (1e5*2+1); public static int k; public static void main (String[] args) { Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in))); int T = scan.nextInt(); for(int i=1; i<=T; i++) { n = scan.nextInt(); k = scan.nextInt(); int K = k; int count=0,z=0; String s = scan.next(); Character[] wall = new Character[n+1]; for (int c = 0; c < n; c++) { wall[c+1] = s.charAt(c); } for(int m=1; m<=n/2; m++){ if(wall[m] != wall[n-m+1]) count++; } if(count == K) z =0; if(count > K) z = count - K; if(count < K) z = K -count; System.out.printf("Case #%d: %d\n",i,z); } } }

Here is the link for Google KickStart Round A 2020 Allocation problem using JAVA.