Problem Description

Given two strings s and t, both consisting of lowercase English letters and digits, your task is to calculate how many ways exactly one digit could be removed from one of the strings so that s is lexicographically smaller than t after the removal.

Note that we are removing only a single instance of a single digit, rather than all instances (e.g., removing 1 from the string a11b1c could result in a1b1c or a11bc, but not abc).

Also note that digits are considered lexicographically smaller than letters.

Examples

Example 1

For s = "ab12c" and t = "1zz456", the output should be removeOneDigit(s, t) = 1.

Here are all the possible removals:

1. We can remove the first digit from s, obtaining "ab2c". "ab2c" > "1zz456", so we don't count this removal
2. We can remove the second digit from s, obtaining "ab1c". "ab1c" > "1zz456", so we don't count this removal
3. We can remove the first digit from t, obtaining "zz456". "ab12c" < "zz456", so we count this removal
4. We can remove the second digit from t, obtaining "1zz56". "ab12c" > "1zz56", so we don't count this removal
5. We can remove the third digit from t, obtaining "1zz46". "ab12c" > "1zz46", so we don't count this removal
6. We can remove the fourth digit from t, obtaining "1zz45". "ab12c" > "1zz45", so we don't count this removal

The only valid case where s < t after removing a digit is "ab12c" < "zz456". Therefore, the answer is 1.

Example 2

For s = "ab12c" and t = "ab24z", the output should be removeOneDigit(s, t) = 3.

There are 4 possible ways of removing the digit:

1. "ab1c" < "ab24z"
2. "ab2c" > "ab24z"
3. "ab12c" < "ab4z"
4. "ab12c" < "ab2z"

Three of these cases match the requirement that s < t, so the answer is 3.

Input/Output

• [execution time limit] 4 seconds (py3)
• [input] string s
  • A string consisting of lowercase English letters and digits 0..9.
  • Guaranteed constraints: 1 ≤ s.length ≤ 10^3.
• [input] string t
  • A string consisting of lowercase English letters and digits 0..9.
  • Guaranteed constraints: 1 ≤ t.length ≤ 10^3.
• [output] integer
  • The number of ways to remove exactly one digit from one of the strings so that s is lexicographically smaller than t after the removal.

Function Signature

def removeOneDigit(s: str, t: str) -> int:
    # Your code here

Sample Test Cases

Test Case 1

Input:

s = "ab12c"
t = "1zz456"

Expected Output: 1

Test Case 2

Input:

s = "ab12c"
t = "ab24z"

Expected Output: 3