performance - 查找字符串中没有重复的最长子字符串。时间复杂度？

Question

我最近面试了一家公司的软件工程职位。我被问到字符串中最长的唯一子字符串的问题。我的算法如下-

从最左边的字符开始，一直将字符存储在哈希表中，键为字符，值为index_where_it_last_occurred。只要该字符不存在于哈希表中，就将其添加到答案字符串中。如果我们再次遇到存储的字符，我会停下来记下长度。我清空哈希表，然后从重复字符的右侧索引重新开始。从 (index_where_it_last_occurred) 标志中检索正确的索引。如果我到达字符串的末尾，我将停止并返回最长的长度。

例如，假设字符串是 abcdecfg。

我从a开始，存储在哈希表中。我存储 b 等等，直到 e。它们的索引也被存储。当我再次遇到 c 时，我停下来，因为它已经被散列并记下长度 5。我清空散列表，并从重复字符的正确索引重新开始。重复的字符是 c，我从位置 3 开始，即字符 d。当我没有到达字符串末尾时，我会一直这样做。

我很想知道这个算法的时间复杂度是多少。 IMO，它将是 O(n^2)。

这是代码。

import java.util.*;
public class longest
{
    static int longest_length = -1;
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        calc(str,0);    
        System.out.println(longest_length);
    }

    public static void calc(String str,int index)
    {
        if(index >= str.length()) return;
        int temp_length = 0;
        LinkedHashMap<Character,Integer> map = new LinkedHashMap<Character,Integer>();
        for (int i = index; i<str.length();i++) 
        {
            if(!map.containsKey(str.charAt(i)))
            {
                map.put(str.charAt(i),i);
                ++temp_length;
            }
            else if(map.containsKey(str.charAt(i)))
            {
                if(longest_length < temp_length)
                {
                    longest_length = temp_length;
                }
                int last_index = map.get(str.charAt(i));
//              System.out.println(last_index); 
                calc(str,last_index+1);
                break;
            }
        }
        if(longest_length < temp_length)
            longest_length = temp_length;
    }
}

Answer 1

如果字母表的大小为 K，那么当您重新开始计数时，您最多会跳回 K-1 个位置，因此您最多读取字符串中的每个字符 K 次。所以算法是O(nK)。

包含 n/K 个字母表副本的输入字符串表现出这种最坏情况的行为。例如，如果字母表是 {a, b, c}，“abcabcabc...abc”形式的字符串具有几乎每个字符都被您的算法读取 3 次的属性。

您可以在 O(K+n) 时间内解决原始问题，使用动态规划使用 O(K) 存储空间。

让字符串为 s，我们将保留一个数字 M，它将是最大的以 i 结尾的 unique_char 字符串的长度，P，它存储每个字符之前出现的位置，并且best，目前为止发现的最长的 unique-char 字符串。

开始:

Set P[c] = -1 for each c in the alphabet.
M = 0
best = 0

然后，对于每个 i:

M = min(M+1, i-P[s[i]])
best = max(best, M)
P[s[i]] = i

这在存储上的复杂度为 O(K)，在运行时上的复杂度为 O(K+n)。