Partial Replacement (Codeforces 1506B)
Tags: Greedy, implementation

You are given a number $$$k$$$ and a string $$$s$$$ of length $$$n$$$, consisting of the characters '.' and '*'. You want to replace some of the '*' characters with 'x' characters so that the following conditions are met:   The first character '*' in the original string should be replaced with 'x';  The last character '*' in the original string should be replaced with 'x';  The distance between two neighboring replaced characters 'x' must not exceed $$$k$$$ (more formally, if you replaced characters at positions $$$i$$$ and $$$j$$$ ($$$i < j$$$) and at positions $$$[i+1, j-1]$$$ there is no "x" symbol, then $$$j-i$$$ must be no more than $$$k$$$). For example, if $$$n=7$$$, $$$s=$$$.**.*** and $$$k=3$$$, then the following strings will satisfy the conditions above:   .xx.*xx;  .x*.x*x;  .xx.xxx.  But, for example, the following strings will not meet the conditions:   .**.*xx (the first character '*' should be replaced with 'x');  .x*.xx* (the last character '*' should be replaced with 'x');  .x*.*xx (the distance between characters at positions $$$2$$$ and $$$6$$$ is greater than $$$k=3$$$). Given $$$n$$$, $$$k$$$, and $$$s$$$, find the minimum number of '*' characters that must be replaced with 'x' in order to meet the above conditions.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 500$$$). Then $$$t$$$ test cases follow.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 50$$$).The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of the characters '.' and '*'.It is guaranteed that there is at least one '*' in the string $$$s$$$.It is guaranteed that the distance between any two neighboring '*' characters does not exceed $$$k$$$.

Output: For each test case output the minimum number of '*' characters that must be replaced with 'x' characters in order to satisfy the conditions above.


Sample Inputs:
5
7 3
.**.***
5 1
..*..
5 2
*.*.*
3 2
*.*
1 1
*

Sample Outputs:
3
1
3
2
1

Solution (Python):
for p in range(int(input())):
    (a, b) = map(int, input().split())
    k = list(input())
    if k.count('*') == 1:
        print(1)
    elif k.count('*') == 2:
        print(2)
    else:
        l = []
        for i in range(a):
            if k[i] == '*':
                l.append(i)
        r = 2
        if l[-1] - l[0] <= b:
            print(r)
        else:
            (p1, p2, f) = (0, 0, 0)
            while 1:
                while l[p1 + 1] - l[p2] <= b:
                    p1 += 1
                    if p1 == len(l) - 1:
                        f = 1
                        break
                (p2, p1) = (p1, p1)
                if f:
                    break
                else:
                    r += 1
            print(r)

Solution (Python):
for t in range(int(input())):
    (n, k) = map(int, input().split())
    s = input()
    l = s.find('*')
    r = s.rfind('*')
    if r == l:
        print(1)
    else:
        cnt = 2
        while r - l > k:
            l = s[:l + k + 1].rfind('*')
            cnt += 1
        print(cnt)

Solution (Python):
for t in range(int(input())):
    (n, k) = map(int, input().split())
    s = input()
    i = 0
    ans = 0
    while i < len(s):
        if s[i] == '*':
            i += 1
            ans = 1
            break
        i += 1
    while i < n:
        if '*' in s[i:i + k]:
            i += s[i:i + k].rindex('*') + 1
            ans += 1
        else:
            break
    print(ans)