时间戳

首页 > 解决方案 > 具有某些属性的最小字符串

algorithm - 具有某些属性的最小字符串

问题描述

假设我有一个包含 N 个正整数的字符串，其中包含 K 个不同的整数。例如这个字符串：1 3 1 3 1 3 3 2 2 1.对于这个字符串 N=10,K=3(1,2,3)。什么我想要的是找到包含所有 K 个整数的最小子字符串。在这种情况下，解决方案将是 1 3 3 2 或 3 2 2 1。

我想过从左到右检查这个字符串并创建一个新字符串。在这个新字符串中，我将第一个整数命名为“first”，并将它的值与我当时正在检查的每个整数进行比较。如果我是关于添加与第一个元素相同我从字符串中删除第一个元素，第一个+1元素成为新的`first。之后我还需要检查第一个（前一个）后面的元素并检查是否为first+ 1 和 first+2..first+n 是相同的（fe 3 3 3）我删除所有这些，除了第 n 个元素。我还可以跟踪属于我正在构建的列表中的不同元素以及它何时达到 K 保持这个值，并且只有在找到一个较小的子集时才更新它。然而，我认为这不是最佳解决方案，我相信这可以在线性时间内以某种方式完成。有什么想法吗？

标签： algorithm

解决方案

这可以肯定地以线性方式完成。

最初，让我们找到命中所有K值的最短前缀，然后我们将删除第一项并扩大新前缀直到命中，依此类推。答案只是这些前缀的最小长度。

cnt[K] = {0, 0, ..., 0} # cnt[i] == how many times we hit value i
nonzero_cnt = 0 # how many different values we hit

hi = 0 # right border
ans = N+1 # len of shortest subsegment found so far, >N on init to be relaxated
for lo = [0, N):  # left border (or how many first elements we droped)
    while nonzero_cnt < N: # moving right border until subsegment is good
        if hi = N: STOP() # right border did all the way to boundary
        if cnt[hi] = 0:
            nonzero_cnt += 1
        cnt[hi] += 1
        hi += 1
    ans = min(ans, hi-lo)
    cnt[lo] -= 1 # left border moved to right by one
    if cnt[lo] = 0:
        nonzero_cnt -= 1

推荐阅读