67

Run dynamic programming separately for $m=6$ and $m=7$. Let $dp_m[r]$ be the maximum length of a nonempty subsequence among the digits processed so far whose remainder modulo $m$ is $r$. A value of $0$ means that no such subsequence exists.

For the next digit $d$, either skip it, start a new one-digit number, or append it to an existing subsequence. Appending to a subsequence with remainder $r$ gives remainder $(10r+d)\bmod m$. Use only states from before processing the digit for these transitions.

After processing all digits, let $L=\max(dp_6[0],dp_7[0])$. If $L=0$, print $-1$. Otherwise, print $N-L$. Each case takes $O(N)$ time and $O(1)$ auxiliary space, excluding the input string.

Proof

Initially, no nonempty subsequence exists, so all states are $0$. After processing the next digit, every possible subsequence either omits it, consists of that digit alone, or appends it to a previous subsequence. The transitions take the maximum over exactly these possibilities, so each state has its claimed maximum length.

A valid number has remainder $0$ modulo $6$ or modulo $7$. Thus $L$ is the maximum number of characters that can remain, and $N-L$ is the minimum number to delete. If $L=0$, no nonempty valid subsequence exists.

For subtask 1, enumerate all nonempty subsequences in $O(N2^N)$ time. For subtask 2, use the position of the last selected digit and the remainder as the state, and transition from every earlier position in $O(N^2)$ time. For the full constraints, keep only the maximum length for each remainder.

Solution written by GPT6