具有大写和相应小写字符的最小窗口(子字符串)

我在现场面试中被问到以下问题:

当字符串中的每个字母都以大写和小写形式出现时,该字符串被认为是“平衡的”。例如,CATattac是平衡的(act在两种情况下都出现),而Madam不是(ad只出现在小写)。编写一个函数,给定一个字符串,返回该字符串的最短平衡子字符串。例如:
“azABaabza”应该返回“ABaab”
“TacoCat”应该返回-1(不平衡)
“AcZCbaBz”应该返回整个字符串

用蛮力方法做它是微不足道的 - 计算所有子串对,然后检查它们是否平衡,同时跟踪最小一个的大小和起始索引。

我该如何优化?我有一种强烈的感觉,它可以通过滑动窗口/双指针方法来完成,但我不确定如何。什么时候更新滑动窗口的指针?

编辑:删除滑动窗口标签,因为这不是滑动窗口问题(如评论中所述)。

以上是具有大写和相应小写字符的最小窗口(子字符串)的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>