c++ - 交换某些字符后，具有给定子字符串最大数量的字符串？

因此，这是我正在经历的面试问题。

我有字符串a, b, and c。我想通过交换k中的一些字母来获取字符串a，以便k应该包含尽可能多的不重叠的子字符串，这些子字符串等于b或c。字符串x的子字符串是由x中的连续字符段组成的字符串。如果字符串x中的两个子字符串在两个字符串i中都占据位置，则它们重叠。

输入:第一行包含字符串a，第二行包含字符串b，第三行包含字符串c(1≤| a |，| b |，| c |≤10 ^ 5，其中| s |表示长度字符串s)。

所有三个字符串仅由小写英文字母组成。

b和c可能重合。

输出:查找可能的字符串k之一。

Example:
I/P
abbbaaccca
ab
aca

O/P
ababacabcc
this optimal solutions has three non-overlaping substrings equal to either b or c on positions 1 – 2 (ab), 3 – 4 (ab), 5 – 7 (aca).

现在，我能想到的方法是为每个字符串创建一个字符计数数组，然后继续进行。基本上，遍历原始字符串(a)，检查b和c的出现。如果不存在，请交换尽可能多的字符以使b或c(以较短的为准)。但是，显然这不是最佳方法。
谁能提出更好的建议？ (仅伪代码就足够了)
谢谢!

最佳答案

首先，您需要计算每个字符串中每个字符的出现次数。 a的出现次数将是您的背包，您需要用它填充尽可能多的b或c。

请注意，当我说背包时，我的意思是a的字符计数 vector ，然后将b插入a将意味着通过a的字符计数 vector 减少b的字符计数 vector 。
我的数学证明有些不足，但是您需要

在背包

中插入尽可能多的b

在背包中插入尽可能多的c(在1后面留有空格)。

如果从背包中删除b将允许插入更多c，则从背包中删除b。否则，请完成。

向背包

填入尽可能多的c

重复3-4。

在整个程序中，计算背包中b和c的数量，输出应为:

[b_count times b][c_count times c][char_occurrence_left_in_knapsack_for_char_x times char_x for each char_x in lower_case_english]

这应该可以解决您在O(n)的问题。