RSSフィードを購読
Python Coding Challenge - How will you find the longest substring without the repeating characters?
(Python コーディングチャレンジ [重複文字を含まない最長のサブ文字列を探そう！] 編)
(Python コーディングチャレンジ [重複文字を含まない最長のサブ文字列を探そう！] 編)
文字列処理における dictionary の活用方法をマスターしましょう！
問題：
アルファベット文字から構成される文字列 s が与えられます。この時、同じ文字を含まない最長のサブ文字列を見つけ、その長さを返すプログラムを記述してください。「サブ文字列」は元の文字列 s の「スライス」であり、文字の並べ替えなどをしてはいけません。
例 1:
与えられる文字列 s: "aaaaa"
# 出力: 1
例 1 の解説:
文字の重複がないサブ文字列は "a" だけです。よって "a" の長さ 1 を返します。
例 2:
与えられる文字列 s: "pwwkew"
# 出力: 3
例 2 の解説:
文字の重複がないサブ文字列は "pw", "wke", "kew" などです。よってこれらの中で最も長い 3 を返します。
また関数定義は以下のような形です (同じである必要はありません):
def length_of_longest_substring(s: str) -> int:
...
...
作成したプログラムは以下のテストをパスする必要があります:
import unittest
class TestLengthOfLongestSubstring(unittest.TestCase):
def test_1(self):
s = 'abcdef'
res = length_of_longest_substring(s)
self.assertEqual(res, 6)
def test_2(self):
s = 'abcdea'
res = length_of_longest_substring(s)
self.assertEqual(res, 5)
def test_3(self):
s = 'abcdab'
res = length_of_longest_substring(s)
self.assertEqual(res, 4)
def test_4(self):
s = 'abcdaeb'
res = length_of_longest_substring(s)
self.assertEqual(res, 5)
def test_5(self):
s = 'aaaaa'
res = length_of_longest_substring(s)
self.assertEqual(res, 1)
def test_6(self):
s = 'pwwkew'
res = length_of_longest_substring(s)
self.assertEqual(res, 3)
if __name__ == '__main__':
unittest.main()
class TestLengthOfLongestSubstring(unittest.TestCase):
def test_1(self):
s = 'abcdef'
res = length_of_longest_substring(s)
self.assertEqual(res, 6)
def test_2(self):
s = 'abcdea'
res = length_of_longest_substring(s)
self.assertEqual(res, 5)
def test_3(self):
s = 'abcdab'
res = length_of_longest_substring(s)
self.assertEqual(res, 4)
def test_4(self):
s = 'abcdaeb'
res = length_of_longest_substring(s)
self.assertEqual(res, 5)
def test_5(self):
s = 'aaaaa'
res = length_of_longest_substring(s)
self.assertEqual(res, 1)
def test_6(self):
s = 'pwwkew'
res = length_of_longest_substring(s)
self.assertEqual(res, 3)
if __name__ == '__main__':
unittest.main()
考え方:
１つの考え方は「力ずく戦略 (brute force strategy)」です。この場合 for ループのネストを実装して与えられた文字列における「全てのサブ文字列」を検証します。
外側のループ left では 0 から与えられた文字列 s の最後まで移動していきます。このポインタで今回取り出すサブ文字列の先頭を押さえておきます。また、内側のループ right に入る前に、重複する文字を検証するためのリスト not_duplicate を作成し s[left] で初期化します。内側のループ right は left + 1 から与えられた文字列 s の最後まで移動しながら、left を先頭とするサブ文字列において重複がないか、もしあればそこまでのサブ文字列の長さはいくつか、を処理していくことになります。
重複文字を含まない最長のサブ文字列を探すプログラム実装例 (力ずく戦略 [brute force approach] 編):
def length_of_longest_substring(s: str) -> int:
max_length = 0
for left in range(len(s)):
not_duplicate = [s[left]]
for right in range(left + 1, len(s)):
if s[right] in not_duplicate:
max_length = max(max_length, len(not_duplicate))
break
not_duplicate.append(s[right])
max_length = max(max_length, len(not_duplicate))
return max_length
max_length = 0
for left in range(len(s)):
not_duplicate = [s[left]]
for right in range(left + 1, len(s)):
if s[right] in not_duplicate:
max_length = max(max_length, len(not_duplicate))
break
not_duplicate.append(s[right])
max_length = max(max_length, len(not_duplicate))
return max_length
Complexity Analysis
(アルゴリズム解析)
Time complexity (実行計算時間):
与えられる文字列の長さを n とすると、外側のループ left は n 回、その度毎に内側のループは n - left 回ずつループします。よって合計ループ回数は n² の式で表されますから最悪計算時間は O(n²) になります。
Space complexity (実行メモリ要求量):
最悪で要素数 n のリストを作成します。よって space complexity は O(n) です。
Sliding window technique を利用した実装：
「力ずく戦略」でも２つのポインタを利用しました。これは正に「処理対象のウィンドウを定義」していることにほかなりません。しかしここではその考え方を一歩進めます; left ポインタを常に 1 つずつ移動させるのではなく、必要に応じて一気に複数ステップ更新させます。
今回は２つのポインタ以外に、重複のない最長のサブ文字列の長さを保存しておくための max_length と、重複文字を検証するための dictionary; char_dict を用意します。また、left / right ポインタとも文字列のインデックス 0 を指すように初期化しておきます。
right ポインタを文字列の最後に向けて動かしていく中で、このポインタが指す文字が char_dict に含まれていなければ (== 重複文字ではない)、「key:value」ペアとして「文字:インデックス番号」を保存し、その時点までの「重複の無いサブ文字列の長さ」として、現在の max_length と現在の left/right ウィンドウに含まれている文字列の長い方の値を保存します。
逆に right ポインタが指す文字が char_dict に含まれていればその文字はこの時点で「重複している」ということですから、この right ポインタまでの文字列に重複文字が含まれないようにするために、left ポインタの値を「その文字のそれまでのインデックス番号 + 1」まで一気に移動します。その後該当する文字のインデックス番号を right で更新します。
この段階で left -> right までのウィンドウに挟まれた文字列には重複する文字が含まれていないことが保証されていますから、この長さと max_length の大きい方を新たな max_length として保存しておきます。
重複文字を含まない最長のサブ文字列を探すプログラム実装例 (sliding window technique を利用した実装 編):
def length_of_longest_substring(s: str) -> int:
char_dict: dict[str, int] = {}
max_length = 0
left = 0
for right in range(len(s)):
c = s[right]
if c in char_dict:
left = char_dict[c] + 1
char_dict[c] = right
max_length = max(max_length, right - left + 1)
return max_length
char_dict: dict[str, int] = {}
max_length = 0
left = 0
for right in range(len(s)):
c = s[right]
if c in char_dict:
left = char_dict[c] + 1
char_dict[c] = right
max_length = max(max_length, right - left + 1)
return max_length
Complexity Analysis
(アルゴリズム解析)
Time complexity (実行計算時間):
与えられる文字列の長さを n とすると for ループは n 回実行されます。Dictionary への挿入、dictionary 内のアイテムの検索は O(1) で実行されますからプログラム全体の最悪計算時間は O(n) になります。
Space complexity (実行メモリ要求量):
最悪で要素数 n の dictionary を作成します。よって space complexity は O(n) です。