查找按字典顺序大于给定字符串的子序列数

Question

>我正在尝试竞争性编码，有一个问题要求我打印大于给定字符串的字符串数量

例如：AB：那么可能的太阳序列是A，B，AB ...其中 b 是唯一较大的一个(注意 ba 不是子序列(

abc：那么可能的子序列是A，B，C，AB，AC，BC，ABC，在这4个中只有4个符合标准。

所以我尝试了这段代码

for(i=0;i<length;i++)
{  
// find the number of permutations
}

但是在这种情况下，我也得到了问题不允许的字符串......那么我如何找到子序列。

Answer 1

根据您的评论，您已经有了一个计算给定输入的所有排列的方法，让我们将此方法称为permutate，它需要一个String并给出一个String[]。

现在，您希望从所有这些排列中丢弃那些在字典上较小或等于给定输入的排列。最后，你想要一个只包含字典顺序更大的排列的集合。

---

我们现在唯一需要的是我们如何在词典上比较String？但这相当容易，因为String已经提供了这样的方法，它被称为compareTo(这是官方文档(。您将它与first.compareTo(second)一起使用，它会根据第一个String在字典上是否小于、大于或等于第二个String返回负值、正值或零值。

因此，我们只需迭代生成的排列，并与compareTo一起检查哪些元素需要丢弃，哪些元素需要保留。

---

下面是一个片段：

String input = "abc";
String[] allPermutations = permutate(input); // Contains [a, b, c, ab, ac, bc, abc]
ArrayList<String> permutationsToKeep = new ArrayList<>();
for (String permutation : allPermutations) {
if (permutation.compareTo(input) > 0) {
// Permutation is lexicographically greater than input, keep it
permutationsToKeep.add(permutation);
}
}
// permutationsToKeep now contains your desired result
// [b, c, ac, bc]