查找可以从字符串中删除的最短子字符串的长度，从而产生唯一性

Question

刚刚在面试的编码挑战中失败了，现在我正在摸不着头脑。如何才能完成这项任务？

给定长度为 n 的字符串 s，任务是找到最短子字符串的长度，删除后，结果字符串仅由不同的字符组成。

这是我完全失败的代码，我没时间了……我至少走上了正确的道路吗？

 from collections import Counter
def findShortestSubstring(s):
char_freq = Counter(s)
targets = {char for char, idx in char_freq.items() if idx > 1}

if not targets:
return 0

min_len = float('inf')
left = 0
window_counts = Counter()

for right, char in enumerate(s):
if char in targets:
window_counts[char] += 1

while all(window_counts[char] > 0 for char in targets):
min_len = min(min_len, right - left + 1)

if s[left] in targets:
window_counts[s[left]] -= 1
left += 1

return min_len
optimized_test_results = {
"aabbcc": findShortestSubstring("aabbcc"),
"abcabc": findShortestSubstring("abcabc"),
"abcd": findShortestSubstring("abcd"),
"abba": findShortestSubstring("abba"),
"aaaabbbbcccc": findShortestSubstring("aaaabbbbcccc"),
"abcabcabc": findShortestSubstring("abcabcabc"),
"aabacbebebe": findShortestSubstring("aabacbebebe"),
"aabc": findShortestSubstring("aabc"),
"abcdefghijklmnopqrstuvwxyz": findShortestSubstring("abcdefghijklmnopqrstuvwxyz"),
"aaaaaaaaaaaaaaaaaaaaaaaa": findShortestSubstring("aaaaaaaaaaaaaaaaaaaaaaaa")
}

Answer 1

这是一种可能的解决方案，即

O(n)

。由于您只能取出一个子字符串，因此它必须从字符串中间的某个位置开始。因此，从字符串的每一端找到唯一的字符，一旦找到所有这些字符，要删除的子字符串的长度就是字符串的长度减去唯一字符的数量。

def findShortestSubstring(s):
    def helper(s):
        l = len(s)
        chars = set()
        # find unique characters going forwards
        i = 0
        while i < l and (c := s[i]) not in chars:
            chars.add(c)
            i += 1
        # if we reached the end of the string, we're done
        if i == l:
            return 0
        # find unique characters going backwards
        i = l - 1
        while i >= 0 and (c := s[i]) not in chars:
            chars.add(c)
            i -= 1
        return l - len(chars)
    
    ml = helper(s)
    if ml == 0:
        return ml
    return min(ml, helper(s[::-1]))

optimized_test_results = {
    "aabbcc": findShortestSubstring("aabbcc"),
    "abcabc": findShortestSubstring("abcabc"),
    "abcd": findShortestSubstring("abcd"),
    "abba": findShortestSubstring("abba"),
    "aaaabbbbcccc": findShortestSubstring("aaaabbbbcccc"),
    "abcabcabc": findShortestSubstring("abcabcabc"),
    "aabacbebebe": findShortestSubstring("aabacbebebe"),
    "aabc": findShortestSubstring("aabc"),
    "abcdefghijklmnopqrstuvwxyz": findShortestSubstring("abcdefghijklmnopqrstuvwxyz"),
    "aaaaaaaaaaaaaaaaaaaaaaaa": findShortestSubstring("aaaaaaaaaaaaaaaaaaaaaaaa")
}
print(optimized_test_results)

输出：

{
    "aabbcc": 4,
    "abcabc": 3,
    "abcd": 0,
    "abba": 2,
    "aaaabbbbcccc": 10,
    "abcabcabc": 6,
    "aabacbebebe": 8,
    "aabc": 1,
    "abcdefghijklmnopqrstuvwxyz": 0,
    "aaaaaaaaaaaaaaaaaaaaaaaa": 23
}

请注意，由于字符串的两端可能具有相同的字符，因此您需要在两个方向上尝试以找到最大数量的唯一字符。例如，对于字符串

aadcba

，当从末尾开始时，

a

已经在

chars

中，因此我们看不到 4 个唯一字符的字符串。通过反转字符串并重新处理，确保我们找到最长的字符串。