You are given a string S made of N digits that represents a positive integer.
Among all positive integers smaller than S, find the one with the maximum possible sum of digits. If there is more than one such integer, return any of them. The returned string can only consist of digits and may not contain leading zeros.
Examples:

1. Given S = "899", one of the possible correct answers is "898".
2. Given S = 10", the only possible correct answer is "9".
3. 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., 100,000];
   • string S is made only of digits (0-9);
   • S does not contain leading zeros.

I have tried but coudn't get better solution than brute force. Is there any optimal way to do this?