字母表的排列，最大限度地减少了构建字符串的子序列的数量

让我们介绍几个术语：

• 移动 - 输入中的两个相邻字母;
• 跳跃 - 字母表允许的动作;
• 重置 - 字母表不允许的动作;

例如，如果 alphabet is 和 input 是：cbacbacaba

• 移动将是：、、、、、c->bb->aa->cc->aa->bb->a;
• 跳跃将是： ，c->bc->a & b->a;
• 重置为：、a->ca->b;

可以很容易地看出，答案是重置次数 + 1。因此，我们关心的只是我们所做的动作是跳跃还是重置。

这使我们能够简化输入——我们只关心 Move（相邻字母对）。我们可以将输入压缩成一个二维矩阵，其中包含每个移动的数量：

For cbacaba:
   a   b   c
a  0   1   1  (a->b & a->c)
b  2   0   0  (b->a x2)
c  1   1   0  (c->a & c->b)

现在我们可以注意到这个矩阵的一个有趣的属性。

如果我们选择一个字母作为字母表的第一个字母，那么我们将把该字母列的总和添加到答案中，因为对该字母的每一次移动都是有保证的重置。此外，该字母行中的数字总和永远不会添加到答案中，因为所有这些动作都保证跳跃。 例如，如果我们以一个字母作为第一个字母：

• a： +3 表示答案 （B->A x2 + C->A），-2 表示潜在答案。（A->B 和 A->C）
• b： +2 表示答案 （A->B + C->B），-2 表示潜在答案。（A->B和C->B）
• c： +1 表示答案 （A->C），-2 表示潜在答案。（C->A和C->B）

现在我们可以选择最佳选项 - 这显然是 ，因为它从表中删除了 2，并且只将 1 添加到答案中。在我们将字母放在字母表的第一位后，我们可以将问题视为其中没有该字母。对于我们的 Moves 矩阵，这意味着我们只需删除相应的行和列。c

您可以重复此操作，一次增加一个字母，直到没有字母为止。按 挑选字母。在这种情况下：Min(Sum(Column) - Sum(Row))

   a   b   c
a  0   1   x  (a->b)
b  2   0   x  (b->a x2)
c  x   x   x 

这意味着作为下一个字母将添加 2 个重置，并且只添加一个。显然，我们应该采取，然后这将给我们一个解决方案，重置的总数为：1（从）+ 1（从）+ 1（原始字母）= 3。abbacbacb

请注意，我尚未测试该解决方案，也无意测试。