Pythonで文字を繰り返さない最長の部分文字列

Question

これはかなり標準的なインタビューの質問です。文字を繰り返さずに最も長い部分文字列を探します。ここにテストケースがあります。

abcabcbb -> 3 
bbbbb -> 1 
pwwkew -> 3 
bpfbhmipx -> 7 
tmmzuxt -> 5 

ここでは2つのポインタでかなり簡単なアプローチを使用して私のコードです。

def lengthOfLongestSubstring(s): 
    checklist = {} 
    starting_index_of_current_substring = 0 
    length_of_longest_substring = 0 
    for i, v in enumerate(s): 
     if v in checklist: 
      starting_index_of_current_substring = checklist[v] + 1 
     else: 
      length_of_current_substring = i - starting_index_of_current_substring + 1 
      length_of_longest_substring = max(length_of_current_substring, length_of_longest_substring) 

     checklist[v] = i 
    return length_of_longest_substring 

私のコードは、最後のものを除くすべてのテストケースを渡します（実際の4、予想される5）。最後のテストケースを処理するためにコードを修正する手助けをすることができますか？私はアルゴリズムを再考したくありません。

Answer 1

ありがとう@ user2357112私はあなたのヒントを理解するためにそれを使用しました。ここで

def lengthOfLongestSubstring(s): 
    checklist = {} 
    starting_index_of_current_substring = 0 
    length_of_longest_substring = 0 
    for i, v in enumerate(s): 
     if v in checklist: 
      if checklist[v] >= starting_index_of_current_substring: 
         starting_index_of_current_substring = checklist[v] + 1 

     length_of_current_substring = i - starting_index_of_current_substring + 1 
     length_of_longest_substring = max(length_of_current_substring, length_of_longest_substring) 
       checklist[v] = i 
    return length_of_longest_substring 

Answer 2

は、文字を繰り返すことなく、最長のサブ文字列を検索するには、2つのポインタを使用して、コードで簡単な微調整です。

チェックリストにvがない場合のコードの変更は、最長の部分文字列の長さを計算する代わりに、すべてのケースで最も長い部分文字列の長さを計算しています。

def lengthOfLongestSubstring(s): 
    checklist = {} 
    starting_index_of_current_substring = 0 
    length_of_longest_substring = 0 
    for i, v in enumerate(s): 
     if v in checklist: 
      starting_index_of_current_substring = max(starting_index_of_current_substring, checklist[v] + 1) 
     checklist[v] = i 
     length_of_longest_substring = max(length_of_longest_substring, i - starting_index_of_current_substring + 1) 
    return length_of_longest_substring 

## Main 
result = {} 
for string in ['abcabcbb', 'bbbbb', 'ppwwkew', 'wcabcdeghi', 'bpfbhmipx', 'tmmzuxt', 'AABGAKGIMN', 'stackoverflow']: 
    result[string] = lengthOfLongestSubstring(string) 
print(result) 

サンプル実行：

{'abcabcbb': 3, 'bbbbb': 1, 'ppwwkew': 3, 'wcabcdeghi': 8, 'bpfbhmipx': 7, 'tmmzuxt': 5, 'AABGAKGIMN': 6, 'stackoverflow': 11}