Assume the the number is $1$ with 6 $9$s and one $8$.
Now $19999999\equiv 5\pmod 7$
If we subtract $10^k $ we will get aus a number with a $1$ , 6$9$ and one $8$ anda different equivalence. so we need to find the $10^k\equiv 5\mod 7$.
$10\equiv 3$
$100\equiv 30\equiv 2$
$1000\equiv 20\equiv 6$
$10,000\equiv 60\equiv 4$
$100,000 \equiv 40\equiv 5$
So $19,999,999-100,000=19,899,999\equiv 0\pmod 7$.
And that's that. It's digits add to $63$ so it's divisible by $9$ and it's divisible by $7$. And beginning with $1$ and the only such divisible by $7$ it's the smallest such number.
====
I thought I made it clear why this is the smallest.
No element with $7$ digits or fewer exist as the OP figured out. For a group with $8$ digits the smallest would start with a $1$. If you have an $8$ digit number beginning with $1$ and whose digits add to $63$ the remaining digits must be six $9$s and one $8$. Such a number can be written as $19,999,999 - 10^k$ where $0\le k \le 7$. For such a number to be divisible by $63$ we must have $10^k \equiv 5 \pmod 7$. The ONLY such $k$ is $k = 5$ and $10^k =100,000$ and the number is $19,899,999$. So this is the only such number divisible by $63$ whose digits add to $63$ in the smallest possible category of types of numbers that can have such numbers. So this is the smallest such number.
The digit sum of $s + 1$ for your number $18999999999999$ is $10$, not divisible by $19$.
If there are $k$ $9$'s at the end of $s$, then the digit sum of $s$ and $s + 1$ differ by $9k - 1$.
Therefore there should be at least $17$ $9$'s at the end of $s$ (as $17$ is the inverse of $9$ modulo $19$). In order for the sum to be divisible by $19$, we should add another $18$. But it is not possible to do that in two digits, as that would require another two $9$'s.
So we must have at least $20$ digits, and the smallest such $s$ is $19899999999999999999$.
Best Answer
You seem to be assuming that the integer is positive and that it’s written in decimal notation. If so, the algorithm is correct and optimal. The case where you write “it is impossible to complete the task” can’t occur, because the number can’t have residue $1$ modulo $3$ unless it contains either at least one digit with residue $1$ or at least two digits with residue $2$.
A problem that can occur, though, is that there are no digits left after you’ve removed some digits. In that case, it is indeed impossible to complete the task (unless we allow the empty digit string to represent $0$).