Say you have a binary (0 or 1 characters) string of N characters. Each character is equally likely to appear. What is the probability that there will be a substring of K 1 characters?

For instance if K = 2, N = 3 the answer is 3/8 = 37.5%.

000: NO
001: NO
010: NO
011: YES
100: NO
101: NO
110: YES
111: YES

How to solve this problem. Can it be done in polynomial time?