Longest Substring Without Repeating Characters - LeetCode を (最終的に Solutions を見て) 3時間かけて解くまでの記録
挑戦開始
https://leetcode.com/problems/longest-substring-without-repeating-characters/ をやる。単に unique にするだけではいけないらしい。
“pwke” is a subsequence and not a substring.
じゃあどうすればいいんだ？1文字ずつ見ていくと言っても、複数文字列を保持できないしな…。並びが大事だから文字ごとにカウントするというわけではなさそうだし…。
Max 文字列から始めていってスライスしていく？文字列そのものと文字列をユニークにしたものの文字列長を比較して、同じ長さであればその長さを返す？それだと "a" * (5 * 10^4 - 1) + "b" みたいな文字列のとき計算量やばそうだな…。でも一回それでやってみるか。
あーだめだった。Time Limit Exceeded だ。 https://leetcode.com/problems/longest-substring-without-repeating-characters/submissions/1102133429/
# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
sl = s.length
sl.downto(1) do |l|
(sl - l + 1).times do |n|
return l if s[n...l+n].chars.uniq.length == l
end
end
end
えー。"mzohydtuotjyysttlknmqdyvdpbxftatuqastvphoahpsdifnxrfbqaghdfoyhhsxhntdcctcmiupqzeqsjrkmzr" これで引っかかるんか…。
先頭から1文字ずつ走査していって、ダブるまでカウントして、ダブったらそのインデックスからやり直すというロジックはどうか？
https://leetcode.com/problems/longest-substring-without-repeating-characters/submissions/1102150407/ だめだった。
# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
sl = s.length
count = 0
index = 0 # 走査開始時インデックス
ans = 0
while index < sl - 1
pp [index, count, s[index..index+count], s[index+count+1]]
count += 1
ans = [ans, count].max
if s[index...index+count].include?(s[index+count])
# 次の文字が現在の文字列に含まれたらその文字から走査しなおす
index = index+count
count = 0
end
end
ans
end
この時点で1時間考えている。もうすぐ1時になる。今日はやめにしよう…。寝る…。
次の日
各文字ごとに出現位置を array で持ち、そのインデックスの差分が一番大きいものが答えじゃないか？→違った。そりゃそうか…。"abcbcbba" みたいなときに 7 - 0 = 7 が答えになるわけないもんな…。
# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
h = {}
s.chars.uniq.map { |c| h[c] = [] }
s.chars.each_with_index do |c, i|
h[c] = h[c].append(i)
end
ans = 0
h.each_value do |a|
(a.length - 1).times do |t|
# pp a
ans = [a[t+1] - a[t], ans].max
end
pp ans
end
ans
end
うーーんわからん。
文字ごとのインデックスを控えるのはいいアイデアなんじゃないか？その間の文字に重複がないインデックスの最大差分を答えにすればいい気がする。
あーなるほど。。そもそも文字が複数出てこないときはどうするんだっていう話もあるな…。
# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
return 1 if s.length == 1
# 各文字の出現位置を記録
h = {}
s.chars.uniq.map { |c| h[c] = [] }
s.chars.each_with_index do |c, i|
h[c] = h[c].append(i)
end
ans = 0
h.each_value do |a|
(a.length - 1).times do |t|
i1 = a[t]
i2 = a[t + 1]
# 各文字の間に重複文字がなければ、インデックスの差分を答えとして記録する
ans = [i2 - i1, ans].max if s[i1..i2].chars.uniq.count == i2 - i1
end
end
ans
end
もう答え見るか…。
https://leetcode.com/problems/longest-substring-without-repeating-characters/solutions/2133524/java-c-a-reall-detailed-explanation/ へー。この問題は Sliding Window を使って解くのか。この解説、1手順ごとに視覚化されてて分かりやすい…！
デクリメントした結果0になった文字は計算外になるから、filter 使って除外するか。
やっと解けたけど理解できてない…。難しかった…。 https://leetcode.com/problems/longest-substring-without-repeating-characters/submissions/1102720103/
# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
i = 0
j = 0
ans = 0
h = {}
while j < s.length
h[s[j]] = 1 + h[s[j]] ||= 0
if h.filter { |_,v| v > 0 }.keys.length == j - i + 1
ans = [ans, j - i + 1].max
end
while h.filter { |_,v| v > 0 }.keys.length < j - i + 1
h[s[i]] -= 1
i += 1
end
j += 1
end
ans
end
(2023/11/21 追記)
Runtime が短い他の Sample Code を参考にして再度挑戦した。 https://leetcode.com/problems/longest-substring-without-repeating-characters/submissions/1103471843/
# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
# 文字列長が2未満であればそのまま答え
return s.length if s.length < 2
char_indexes = {}
start = ans = 0
s.chars.each_with_index do |c, i|
# 記録済の文字出現時
if char_indexes[c]
# 文字の出現位置が start より大きければ、その文字は現在の substring 内の文字と重複している
# そのため start を文字出現位置の次に移動させる
start = char_indexes[c] + 1 if char_indexes[c] + 1 > start
end
# 部分文字列の長さ
substring_length = i + 1 - start
# 最長の更新
ans = [ans, substring_length].max
# 文字の出現位置を記録
char_indexes[c] = i
end
ans
end
