문자열에서 반복없이 가장 긴 하위 문자열 찾기. 시간 복잡성?

Question

저는 최근에 소프트웨어 엔지니어링 분야의 회사와 인터뷰했습니다. 문자열에서 가장 긴 고유 한 하위 문자열에 대한 질문을 받았습니다. 내 알고리즘은 다음과 같습니다 -

가장 왼쪽 문자부터 시작하여 키가 character이고 값이 index_where_it_last_occurred 인 해시 테이블에 문자를 계속 저장하십시오. 해시 테이블에없는 한 응답 문자열에 문자를 추가하십시오. 저장된 문자를 다시 만나면 길이를 멈추고 메모합니다. 해시 테이블을 비운 다음 반복되는 문자의 오른쪽 인덱스에서 다시 시작합니다. 올바른 색인은 (index_where_it_last_occurred) 플래그에서 검색됩니다. 문자열의 끝에 도달하면 멈추고 가장 긴 길이를 반환합니다.

예를 들어, 문자열이 abcdecfg이라고 말합니다.

나는 a으로 시작하여 해시 테이블에 저장합니다. 나는 e까지 b 등등을 저장한다. 그들의 색인도 저장됩니다. 내가 다시 c을 만났을 때, 이미 해시 된 이후로 멈 춥니 다. 길이가 5 인 것을 메모합니다. 해시 테이블을 비우고 반복 된 문자의 오른쪽 인덱스에서 다시 시작합니다. 반복되는 문자가 c 인 경우, 다시 위치 3부터 시작합니다. 문자 d. 나는 끈의 끝에 도달하지 않는 동안 이것을 계속하고있다.

이 알고리즘의 시간 복잡도에 대해 알고 싶습니다. IMO, O (n^2)가됩니다.

이것은 코드입니다. 알파벳의 크기가 K 인 경우는 계산 다시 시작할 때 대부분의 K 시간에 문자열의 각 문자를 읽을 수 있도록

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-1 곳에서 점프. 알고리즘은 O (nK)입니다.

알파벳의 n/K 복사본을 포함하는 입력 문자열은 이러한 최악의 경우의 동작을 나타냅니다. 예를 들어 알파벳이 {a, b, c} 인 경우 "abcabcabc ... abc"형식의 문자열에는 거의 모든 문자가 알고리즘에 의해 3 번 읽혀지는 속성이 있습니다.

동적 프로그래밍을 사용하여 O (K) 저장 공간을 사용하여 O (K + n) 시간의 원래 문제를 해결할 수 있습니다.

문자열을 s으로하고, 이전에 각 문자가 표시된 위치를 저장하는 i, P로 끝나는 최대 unique_char 문자열 길이 인 M을 유지하고 best, 가장 긴 고유 문자 길이는 best입니다. char 문자열이 지금까지 발견되었습니다.

시작 :

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

후, 각 I : 이는 스토리지 O (K)의 사소하고, 실행 시간에 O (K + N)

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

.