Given 2 strings, remove only one digit to make 1 string lexicographically smaller

I am trying to work through a coding problem of string manipulation in Java. The question is that

Given two strings S and T consisting of digits and lowercase letters, you are allowed to remove only one digit from either string, count how many ways of removal to make S lexicographically smaller than T.

I came up with this test case myself. If s = ‘3ab’ and t = ‘cd’, return 1. If s = ‘123ab’ and t = ‘423cd’, return 6.

My idea is to use 2 for loops and go through each string by checking if a char is digit, remove it and compare with the other string.

private static int numSmaller(String s, String t){
    int ways = 0;

    for(int i = 0; i < s.length(); i++){
        StringBuilder sbs = new StringBuilder(s);
        if(Character.isDigit(s.charAt(i))){
            sbs.deleteCharAt(i);
            String sub = sbs.toString();
            if(sub.compareTo(t) < 0) {
                ways++;
            }
        }
    }

    for(int i = 0; i < t.length(); i++){
        StringBuilder sbt = new StringBuilder(t);
        if(Character.isDigit(t.charAt(i))){
            sbt.deleteCharAt(i);
            String sub = sbt.toString();
            if(s.compareTo(sub) < 0){
                ways++;
            }
        }
    }
    return ways;
}

As you can see the space complexity is pretty bad, and the code also seems redundant. Is there a way to optimize this piece of code? Does anyone see a way to not use a string builder or create a new string each time? Any input is appreciated!

Answer

I did it using streams and compared it to your approach with random strings of length 10. I ran 1 million test cases of those strings and the two methods provided the same results.

The stream part is fairly straightforward. I use an IntStream to index into a string to build substrings based on digit location. Then I filter based on a passed BiFunction lambda that acts as a two argument predicate. Filtering on that I count the successes.

I do this twice, reversing the arguments and the predicate logic, and sum up the two counts.

long count = count(s1, t1, (a, b) -> a.compareTo(b) < 0);
count += count(t1, s1, (a, b) -> b.compareTo(a) < 0);   

public static long count(String s, String t, BiFunction<String, String, Boolean> comp) {

      return IntStream.range(0, s.length()).filter(
        i -> Character.isDigit(s.charAt(i))).mapToObj(
              i -> s.substring(0, i) + s.substring(i + 1)).filter(
                    ss -> comp.apply(ss, t)).count();
}