Google kickstart solutions k goodness string python

 

GOOGLE KICKSTART PRACTICE

K-GOODNESS 
 STRING 

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.

Testcases1:

Input:

 CABABC 

OUTPUT:

2

Testcases2:

INPUT

ABCAA

OUTPUT:

3

Testcases3:

Input:

ABAB

OUTPUT:

1

In this program you have to count number of operation .

So first understand that the what question is saying .So In this program first you have to input string .And you have to check every element of the string that we have to compare  between starting and  ending value and this ending value,this process will continue 0 to n (means where value n<length ) .

You understand by example:

If the length of string is 5

So it will check 

Index value 0 to len(String)-1=4

Index value 1 to len(String)-2=3

Index value 2 to len(String)-3=2

Only this process you have to do after that you don't have to check for any other index value of the string ,if the left side value is greater than right side value then stop program.

Steps to follow:

1.First you have to input string .

2.Then take value of j i.e length of the given string and also for L.

3.Now take a for loop to access every element to compare the characters of starting value to opposite of from ending index value of the string.

4.If any character is not matched then increase the value of goodness by 1,and also decrease the value of j by -1.and value of i > j then suddenly break the loop to compare the characters.

5.Now you have got goodness value so use print() function to print number of operations required i.e goodness-1.

 

"""

    Write a program to count number of operation in string 

    K-Goodness String

"""

    #Let understand the program and intialize by reading the question.

    #First we take input of any string of capital or string .

    #So here we will use input()function  to take input as a string.

    

    

    

    

    

    s=input("Enter a string:")

    #Then use j variable and assign lenght of the input string

    j=len(s)

    

    #Here goodness is zero and if the two alphabets are same then it will count

    goodness=0

    #L is also assign for length of string for running the loop

    L=len(s)

    #Now take a for loop to access every element upto length of the string

    for i in range(L):

    #we will check i index value to length-1 index value of the string if the both character is not same then goodness is equal +1

        if s[i]!=s[L-1-i]:

    #the value of j will decrease by number of loop will run it means if first time loop run then value of j will decrease by -1

            j=j-1

            

            goodness+=1

    #Now if the value i will increase at any time then stop the loop this is the main thing that you have remember 

        if i>j:

            break

            

    #Now use print() function to print number of operation i.e goodness-1 you have to require to change that character      

    print("The number of operations is ",goodness-1)

Let us understand how this program run  i.e flow of control to count number of operation.

First take example :

s=ABAB

lenght=4

how loop run and check

i =0          compare with   j= len(s)-1-i=4-1-0=3

it means here index value of 0 compare with index value of 3

i.e A=B no, so goodness=goodness+1=1

Then 

i=1          comapare with  j= len(s)-1-i=4-1-1=2

it means here index value of 1 compare with index value of 2

i.e B=A no,then goodness=goodness+1=1+1=2

Then 

i=2 compare with    j= len(s)-1-i=4-1-2=1 but here it will stop 

because value i>j .

So then the Number of operation is =goodness-1=2-1=1

I hope you have understood the logic of program and if you have better solution then write in comment box so that other person can easily understand.