Coding Problems : Google Kick Start 2021 ~ Apna Coding Adda

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 $S_{i} \neq S_{N - i + 1}$ where $1 \leq i \leq N / 2$ ( $1$ -indexed). For example, the string CABABC has a goodness score of $2$ since $S_{2} \neq S_{5}$ and $S_{3} \neq S_{4}$ .

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 \leq T \leq 100$
$0 \leq K \leq N / 2$ .

Test Set 1

Time limit: 20 seconds.
$1 \leq N \leq 100$ .

Test Set 2

Time limit: 40 seconds.
$1 \leq N \leq 2 \times 10^{5}$ for at most $10$ test cases.
For the remaining cases, $1 \leq N \leq 100$ .

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 😊😊

Apna Coding Adda

Coding Problems : Google Kick Start 2021