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

#### Tags: java, lexicographic-ordering, string

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!

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();
}
```

Source: stackoverflow