Skip to main content

Coding Problems : Google Kick Start 2021

 Here i am gonna cover coding problem which was asked in Google kick start competition 2021 in Round A, Let' Begin.



Here are All Detail about problem,

Problem

Charles defines the goodness score of a string as the number of indices i such that where (-indexed). For example, the string CABABC has a goodness score of  since  and .

Charles gave Ada a string  of length , consisting of uppercase letters and asked her to convert it into a string with a goodness score of . 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 ?

Input

The first line of the input gives the number of test cases,  test cases follow.

The first line of each test case contains two integers  and . The second line of each test case contains a string  of length , consisting of uppercase letters.

Output

For each test case, output one line containing Case #, where  is the test case number (starting from 1) and  is the minimum number of operations required to transform the given string  into a string with goodness score equal to .

Limits

Memory limit: 1 GB.

.

Test Set 1

Time limit: 20 seconds.
.

Test Set 2

Time limit: 40 seconds.
 for at most  test cases.
For the remaining cases, .

Let's Code then,

C++:

#include<iostream>
#include<string>
#include<cstdlib>
using namespace std;
int kgoodnessstring(string s,int k){
int count = 0;
int n = s.size();
for(int i=0;i<n/2;i++){
if(s[i]!=s[n-i-1]){
count++;
}
}
return abs(count-k);
}
int main(){
int t;
cin >> t;
int n,k;
for(int i=0;i<t;i++){
cin >>n>>k;
string s;
cin >> s;
cout << "Case #"<<i+1<<": "<<kgoodnessstring(s,k)<<"\n";
}
}

Python3:

def kgoodnessString(s,k):
count = 0
n = len(s)
for i in range(n//2):
if s[i] != s[n-i-1]:
count+=1
return abs(count-k)

t = int(input())
for i in range(t):
n,k = input().split()
n = int(n)
k = int(k)
s = input()
ans = kgoodnessString(s,k)
print(f"Case #{i+1}: {ans}")


Thank You 😊😊


Comments

Popular posts from this blog

Makefile

 You may have seen file named Makefile or you may have type command like make, make install. so what is this file Makefile and what are this command. let's discuss about it.

Products Which I like

Induction Buy now Induction Buy now

Pascal's Triangle

 Pascal's Triangle Introduction In mathematics, Pascal’s triangle is triangular array of binomial coefficient. below you can see how it looks like… 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 How to Build it? First of all start with “1” and second rows as “1 1” then we can clearly see every element in next rows(except 1) if sum of two elements from above row. (i.e, 1+1=2, 1+2=3, 1+3=4) and with this rules we can create pascal’s triangle of n rows. Below is visual of how it will look like, Formula let’s take 0th row as first row and 0th column as first column, so we can get each value using formula where n is row number and k is column number. so for finding 1st(0 indexed) element in 2nd row we can write 2C1 which will give 2. There is one another technique, in which we need to solve (x + y)^n for nth row, if we solve (x +y)² then we will get 2nd row as coefficient of x and y in this solved formula which is x² + 2xy + y² . coefficients are (...