From fc5018e308297220719becf5bf6b36e08d9f4545 Mon Sep 17 00:00:00 2001
From: akmhmgc <akimuhamaguchi@icloud.com>
Date: Sat, 4 Oct 2025 14:27:49 +0900
Subject: [PATCH] 3

---
 3/step1.md | 29 +++++++++++++++++++++++++++++
 3/step2.md | 21 +++++++++++++++++++++
 3/step3.md | 17 +++++++++++++++++
 3/step4.md |  1 +
 4 files changed, 68 insertions(+)
 create mode 100644 3/step1.md
 create mode 100644 3/step2.md
 create mode 100644 3/step3.md
 create mode 100644 3/step4.md

diff --git a/3/step1.md b/3/step1.md
new file mode 100644
index 0000000..3d10db4
--- /dev/null
+++ 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
new file mode 100644
index 0000000..e335de4
--- /dev/null
+++ 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
new file mode 100644
index 0000000..96c986c
--- /dev/null
+++ 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
new file mode 100644
index 0000000..5941ee1
--- /dev/null
+++ b/3/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正