You are given a string $S$ made of $N$ digits that represents a positive nteger.

pong all positive integers smaller than $S,$ find the one with th $m$ imum possible sum of digits.

Wrii a function:

hass Solution $($ public String solution$($St ing S$)$:

that, give. a string $S,$ returns a string representing positive integer smaller the $nS$ with the maximum possible sum of digits. If there is more than one such integer, return any of them the retumed string can only consist of digits and may not contain lea ing zeros.

Examples:

Given $S=899",$ one of the possible correct answers is $"898".$

Given $S=10",$ the only possible correct answer is $"9".$

Given $S="98",$ the only possible correct answer is $"89".$

Write an efficient algorithm for the following assumptions:

$N$ is an integer within the range $[2\mathrm{.}100,000]$;

string $S$ is made only of digits $(0-9)$;

$S$ does not contain leading zeros.

With python code