string - 删除子字符串中所有出现的测试用例

Question

上周我为我的大学举办了一场黑客马拉松事件，如果给定一个字符串，我们需要删除子字符串的第一次出现或最后一次出现，

示例 s= "acaaac"和 t = "a"s 是主串 t 是子串

s 可以是“caaac”或“acaac”，我们需要找到给定 s 和 t 的最大移动次数

输入仅包含小写字母 [a-z]

测试用例 1:s="aabb"和 t = "ab",去掉 "aabb"中出现的 t s 变成 "ab"接下来去掉唯一出现的字符串得到 s =""由于 t 的 s 中不再出现，我们返回 2

测试用例 2:s="aabcd"t = "abc"--->只有一次出现所以计数为 1,

测试用例 3:s="aa"t = "b"计数 =0

我尝试在 java 中遵循伪代码

 count = 0   
 while(s.contains(t))
 {
 s=s.replacefirst(t,"")
 count++;
 }
 return count;

但我没有得到我缺少的测试用例，我在我的事件中通过了 14 个中的 9 个

我能知道我缺少哪些测试用例吗？

Answer 1

这是您的代码将给出错误答案的示例:

s=ababaa , t=aba

您将删除第一次出现的结果，结果是:

(aba)baa -> baa -> 1

但是，如果您先删除第 2 个匹配项，那么您可以删除一个额外的子字符串:

ab(aba)a -> aba -> '' -> 2

看来你必须遍历第一个/最后一个删除的所有可能组合并选择最佳结果。

更有趣的问题是是否有更好的算法而不是暴力破解？