#C10619. Longest Subarray with Digit Sum Constraint

    ID: 39844 Type: Default 1000ms 256MiB

Longest Subarray with Digit Sum Constraint

Longest Subarray with Digit Sum Constraint

You are given an integer N denoting the length of a string S that consists only of digits, and an integer K. Your task is to find the length of the longest contiguous subarray (substring) of S such that the sum of the digits in that subarray is at most K.

Mathematically, you need to find the maximum value of l such that there exists indices i and j satisfying:

$$\sum_{t=i}^{j} d_t \le K \quad \text{and} \quad j-i+1 = l, $$

where dt is the digit at the t-th position in S. If no such subarray exists, output 0.

Note: A contiguous subarray is a sequence of characters in S that appear consecutively.

inputFormat

The input is read from stdin and consists of two lines. The first line contains two space-separated integers N and K. The second line contains a string S of length N which consists of digit characters (0-9).

Example:

5 10
12345

outputFormat

Output a single integer that is the length of the longest contiguous subarray of S such that the sum of its digits is at most K. The result should be printed to stdout.

Example:

4
## sample
5 10
12345
4

</p>