akmhmgc · akmhmgc · Oct 4, 2025 · tokuhirat · Oct 4, 2025
diff --git a/3/step1.md b/3/step1.md
@@ -0,0 +1,29 @@
+# step1 何も見ずに解く
+文字を前から一つずつみていって、開始時点から今見てるところまでの文字列がすべてユニークな文字を含む文字列かどうかをチェックしたい。
+見た文字を管理すれば今見ている文字が既に見たことあるかどうかがわかる。
+既に見た文字があるとき、この文字を含む場合どこまで後ろであれば問題ないかを知りたい。
+例えばabcdec....という文字列がある時に、二回目のcが来た時にdecは問題ないので次を見に行く、ということをしたい。
+それを実現するには、今見ている文字がなくなるまで開始時点を進めればよい。
+こういう感じの発想でいけるはず。
+
+時間計算量はO(N)で空間計算量もO(N)
+Nの最大値は5 * 10^4なので1秒以内に終わる。
+
+```ruby
+# @param {String} str
+# @return {Integer}
+def length_of_longest_substring(str)
+    chars_in_substr = Set.new
+    l = 0
+    res = 0
+    str.size.times do |r|
+        while chars_in_substr.include?(str[r])
+            chars_in_substr.delete(str[l])
+            l += 1
+        end
+        chars_in_substr << str[r]
+        res = [res, r - l + 1].max
+    end
+    res
+end
+```
diff --git a/3/step2.md b/3/step2.md
@@ -0,0 +1,21 @@
+# step2 他の方の解答を見る
+https://github.com/olsen-blue/Arai60/pull/49
+ハッシュテーブルを使う方法
+
+```ruby
+# @param {String} str
+# @return {Integer}
+def length_of_longest_substring(str)
+    visited_char_to_index = Hash.new(-1)
+    max_length = 0
+    left = 0
+    str.size.times do |right|
+        left = [left, visited_char_to_index[str[right]] + 1].max
+        max_length = [max_length, right - left + 1].max
+        visited_char_to_index[str[right]] = right
+    end
+    max_length
+end
+```
+
+こっちの方がシンプルでわかりやすいかも
diff --git a/3/step3.md b/3/step3.md
@@ -0,0 +1,17 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+# @param {String} str
+# @return {Integer}
+def length_of_longest_substring(str)
+    visited_char_to_index = Hash.new(-1)
+    max_size = 0
+    left = 0
+    str.size.times do |right|
+        left = [left, visited_char_to_index[str[right]] + 1].max
+        max_size = [max_size, right - left + 1].max
+        visited_char_to_index[str[right]] = right
+    end
+    max_size
+end
+```
diff --git a/3/step4.md b/3/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		## step4 レビューを受けて解答を修正