具有大写和相应小写字符的最小窗口(子字符串)
我在现场面试中被问到以下问题:
当字符串中的每个字母都以大写和小写形式出现时,该字符串被认为是“平衡的”。例如,
CATattac是平衡的(a,c,t在两种情况下都出现),而Madam不是(a,d只出现在小写)。编写一个函数,给定一个字符串,返回该字符串的最短平衡子字符串。例如:
“azABaabza”应该返回“ABaab”
“TacoCat”应该返回-1(不平衡)
“AcZCbaBz”应该返回整个字符串
用蛮力方法做它是微不足道的 - 计算所有子串对,然后检查它们是否平衡,同时跟踪最小一个的大小和起始索引。
我该如何优化?我有一种强烈的感觉,它可以通过滑动窗口/双指针方法来完成,但我不确定如何。什么时候更新滑动窗口的指针?
编辑:删除滑动窗口标签,因为这不是滑动窗口问题(如评论中所述)。