Company: citadel_3aug
Difficulty: medium
Count Valid Prefix Sequences Problem Description Given a binary sequence of length n as a string, you can perform the following operation any number of times: Append either a '0' or a '1' to the end of the sequence. A sequence is considered valid if it is possible to make the total number of "10" subsequences in the updated sequence exactly equal to k . Your task is to count the total number of valid non-empty prefix sequences of the given binary sequence. Notes: A sequence is a subsequence if it can be obtained by deleting digits (possibly none) from the original sequence without altering the relative positions of the remaining digits. A non-empty prefix sequence is any sequence derived by deleting digits from the end of the given sequence, ensuring the length of the prefix is at least 1. Examples Example 1: Input: sequence = "100", k = 1 Output: 2 Explanation: The analysis of non-empty prefix sequences is as follows: Prefix "1": It has 0 "10"s and one '1'. We need to reach k=1. We ca