if i understood your Java code correctly you are looping through all chars and that's a lot of unnecessary code. if the missing character is at the end then that character is the checksum which is recoverable in a couple of very simple steps:
- replace the missing char with anything from the charset (like 1)
- decode the result using Base58 encoding (not Base58check which is usually the method used to check and remove checksum)
- remove the last 4 bytes
- now encode this result with Base58check
you have the key!
this works for 1 to 4 or probably up to 6 missing characters at the end.
ps. i don't think @JBRai problem is with 1 char or even that char being at the end.