查找字符串中不重复的最长子字符串.时间复杂性

Question

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

从最左边的字符开始，将该字符存储在哈希表中，键为character，值为index_where_it_last_occurred。只要哈希表中不存在该字符，就将其添加到答案字符串中。如果我们再次遇到存储的字符，我会停下来记下长度。我清空哈希表，然后从重复字符的右侧索引重新开始。右侧索引是从（index_where_it_last_occured）标志中检索的。如果我到达绳子的末端，我会停下来，返回最长的长度。

例如，假设字符串为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）存储空间，可以在O（K+n）时间内解决原始问题。

设字符串为s，我们将保留一个数字M，它将是以i结尾的最大unique_char字符串的长度，p存储每个字符以前看到的位置，best是迄今为止发现的最长的唯一字符字符串。

开始：

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）。