Array
K-alternating String
Practice Problems
Assignment Questions
Assignment Questions
Problem Statement
You have been given a binary string S of size N. You also have been given an integer K(1<=k<=N). You
have to print the minimum number of flips(Change an occurrence of ‘1’ to ‘0’ or vice versa) required to
make at least one substring of size K alternating(A binary string is alternating if no two consecutive
characters are the same). For example “10101”, “0101”, “1”, and “0” are examples of alternating binary
strings but “11010”, “01001”, and “00” are not.
Note: A substring is a contiguous sequence of characters within a string.
Constraint
1 t 103
1 K N 10
0 S[i] 1, (i.e S will only contain 0’s and 1’s)
Time Limit:- 1s for C++
Input Format
First-line contains a single integer t, the number of test cases.
The first line of each test case contains two integers N, and K , the size of string S, and the size of
substring we want to make alternating.
The second line of each test case contains a binary string S.
The sum of N over all test cases doesn’t exceed 2*105
Output Format
For each test case, output a single line— the minimum number of flips required to make at least one
substring of size K alternating.
Sample Input
1 1
5 3
10101
5 3
11001
6 2
111111
6 6
110011
Assignment Questions
Sample Output
Explanation of Sample
Note: For sample test explanation we have considered that the indexing of string S is 1-based.
Test case 1: Here S=”0”, this is already an alternating string, So we need 0 flips.
Test case 2: Here S=”10101”, If we pick a substring of size 3 starting from position 1, then it will be “101” and
it is already alternating, so we need 0 flips.
Test case 3: Here S=”11001”, If we flip an 0 at position 4 then string S=”11011”.Now if we pick a substring of
size 3 starting from position 2, then it will be “101” which is an alternating string, So we need 1 flip.
Test case 4: Here S=”111111”, If we flip a 1 at position 3 then string S=”110111”.Now if we pick a substring of
size 2 starting from position 3, then it will be “01” which is an alternating string, So we need 1 flip.
Test case 5: Here S=”110011”, If we flip the characters at positions 2, 3, and 6 then string S=”101010”.Now if
we pick a substring of size 6 starting from position 1, then it will be “101010” which is an alternating string,
So we need 3 flips.
Array
K-alternating String
Practice Problems
Assignment Solutions
Assignment Solutions
JavaScript Code:
let limitOnN;
//Give static input
function solve() {
let n, k;
limitOnN += n;
let s = [];
let v = [];
for (let i = 0; i < n; i++) {
let one = (s[i] == '1');
v[i] = (i % 2) ^ one;
if (i != 0) {
v[i] += v[i - 1];
let ans = k;
for (let i = 0; i + k <= n; i++) {
let l = i,
r = i + k - 1;
let tot = v[r];
if (l != 0)
tot -= v[l - 1];
ans = [Link](
ans,
tot,
k - tot
);
[Link](ans, cel)
JS Fiddle: [Link]
