#C10619. Longest Subarray with Digit Sum Constraint
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>