Finden Sie die Anzahl der Teilsequenzen, die größer als eine andere Zeichenfolge sind ⇐ Java

[Guest]

Gegeben sind zwei Zeichenfolgen s der Länge m und eine weitere Zeichenfolge t der Länge n. Zählen Sie, wie viele Teilfolgen von s größer als t sind.

Eine Folge p ist wird größer als eine andere Folge q genannt, wenn sie
die folgenden Fälle erfüllt:
a) p > q an der ersten Position, an der sich p und q unterscheiden, oder
b) |p| > |q| und q ist ein Präfix von p (wobei |p| die Länge des Passworts p angibt).

Beispiel:
s ="bab"
t ="ab"
Ergebnis = 5
Erklärung:
Valid subsequences of s which are greater than t are
"b"
"ba"
"bb"
"bab"
"b"

Einschränkungen:
Länge von s 1 bis 10^5
Länge von t 1 bis 100
Die Länge von t kann auch bei gültigen Kombinationen größer als die Länge von s sein.
Ich habe es mit einem rekursiven Ansatz gelöst, aber es benötigt O(2^n * n) Zeitkomplexität.
public class Main {
private static final int MOD = 1_000_000_007;

private static void subsequence(String s, int index, String current, List subsequences) {
if (index == s.length()) {
if (!current.isEmpty()) {
subsequences.add(current);
}
return;
}
subsequence(s, index + 1, current, subsequences);
subsequence(s, index + 1, current + s.charAt(index), subsequences);
}

private static boolean isGreater(String s1, String t) {
int len1 = s1.length();
int len2 = t.length();
for (int i = 0; i < Math.min(len1, len2); i++) {
if (s1.charAt(i) > t.charAt(i)) {
return true;
} else if (s1.charAt(i) < t.charAt(i)) {
return false;
}
}
return len1 > len2;
}

public static int solve(String s, String t) {
List subsequences = new ArrayList();
subsequence(s, 0, "", subsequences);

int count = 0;
for (String e : subsequences) {
if (isGreater(e, t)) {
count = (count + 1) % MOD;
}
}

return count;
}

public static void main(String[] args) {
System.out.println(solve("aba", "ab")); // Expected: 3
System.out.println(solve("bab", "ab")); // Expected: 5
System.out.println(solve("wrrmkhds", "bebbjvcgzlwtbvasphvm")); // Expected: 255
System.out.println(solve("o", "h")); // Expected: 1
}
}

Wie kann dies mit weniger Zeitaufwand gelöst werden?