Problem · String
Valid Binary Prefix
Given a binary sequence of length n as a string, 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, without altering the relative positions.
- 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
01 · Example 1
sequence = "100" k = 1 return = 2
Analyze all non-empty prefix sequences:
| Prefix Sequence | Appended String | Sequence Formed After Append | Is Good? |
|---|---|---|---|
"1" | "01" | "101" | Good (There are k "10" sequences) |
"10" | Blank | "10" | Good (There are k "10" sequences) |
"100" | -- | -- | Not Good (Not possible) |
For "100", there are already 2 subsequences of "10": indices (0, 1) and indices (0, 2). Hence, the number of non-empty prefix sequences of the given binary sequence is 2.
Return 2.
More Goldman Sachs problems
public int countValidBinaryPrefixes(String sequence, int k) {
// write your code here
}
sequence"100"
k1
expected2
checking account