查找大于另一个字符串的子序列数

Question

给定两个长度为 m 的字符串 s 和另一个长度为 n 的字符串 t，计算 s 有多少个子序列大于 t

如果满足以下条件，则称序列 p 大于另一个序列 q 以下情况：

a) p[i] > q[i] 在 p 和 q 不同的第一个位置，或者
b) |p| > |q| q 是 p 的前缀（其中 |p| 表示密码 p 的长度）。

示例：

s =“bab” t =“ab”

结果 = 5

说明：

s 大于 t 的有效子序列是 “b” “吧” “bb” “巴巴” “b”

限制： s 的长度 1 到 10^5 t 的长度 1 到 100

我使用递归方法解决了它，但它需要 O(2^n * n) 时间复杂度。

public class Main {
    private static final int MOD = 1_000_000_007;

    private static void subsequence(String s, int index, String current, List<String> 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<String> 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
    }
}

如何以更小的时间复杂度解决这个问题？

Answer 1

看起来你只能找到第一个字母

s[i] > t[i]

，以及最后一个

s[j] > t[i]

。您可以使用两个指针在

O(m)

时间内完成此操作。您还将创建一个辅助列表，其中包含小于

t[i]

的字母索引。将此列表称为

x

。

然后使用简单的数学来确定从第一个不匹配开始到

x

的每个元素可以形成多少个子序列。

在您的示例中，第一个不匹配位于索引 0 处，最长子序列的长度为 3，并且

x=[1]

。因此，对于索引

0

和

1

（包含），您可以形成

2C1+2C2=3

子序列。由于您只需添加一个字符，即

s[2]

，因此您有一个以

s[2]

结尾的子序列，而

s[2]

本身总共给您 5 个字符。如果在

x[1]

之前还有两个字符，那么您就会有另外 2 个以这些字母结尾的序列，加上该组本身还有 3 个序列。