Summary Power

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You work as an engineer. You were given an empty board with $K$ consecutive cells; at any moment, each cell can display one character. You want the board to display a string $S$ with length $N > K$. Since the board isn't large enough, you want to display the string in $NK+1$ steps. In the $i$th step ($1 \le i \le NK+1$), you'll make the board display the characters $S_i, S_{i+1}, \dots, S_{i+K1}$. The power required to switch the board from step $i$ to step $i+1$ (for $1 \le i \le NK$) is equal to the number of characters displayed on the board that have to change between these steps. You should find the total power required for the whole process of displaying a string, i.e. the sum of powers required for switching between all consecutive pairs of steps. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $K$.  The second line contains a single string $S$ with length $N$. ### Output For each test case, print a single line containing one integer — the total power required for text switching. ### Constraints  $1 \le T \le 1,000$  $2 \le N \le 10^5$  $1 \le K \lt N$  each character of $S$ is a lowercase English letter  the sum of $N$ for all test cases does not exceed $10^6$ ### Subtasks **Subtask #1 (20 points):**  $1 \le T \le 100$  $2 \le N \le 50$ **Subtask #2 (80 points):** original constraints ### Example Input ``` 3 6 3 aabbcc 5 2 abccc 4 3 aabb ``` ### Example Output ``` 4 3 1 ``` ### Explanation **Example case 1:**  In step $1$, the board is displaying "aab".  In step $2$, the board is displaying "abb".  In step $3$, the board is displaying "bbc".  In step $4$, the board is displaying "bcc". The power required for switching from the $1$st to the $2$nd step is $1$, because cell $1$ changes from 'a' to 'a' (requiring power $0$), cell $2$ changes from 'a' to 'b' (requiring power $1$) and cell $3$ changes from 'b' to 'b' (requiring power $0$); $0 + 1 + 0 = 1$. The power required for switching between the $2$nd and $3$rd step is $2$ and the power required for switching between the $3$rd and $4$th step is $1$. Therefore, the answer is $1 + 2 + 1 = 4$.Author:  isaf27 
Editorial  https://discuss.codechef.com/problems/SUMPOWER 
Tags  easy, isaf27, isaf27, likecs, ltime61, prefixsum, slidingwindow 
Date Added:  24062018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions