問題: Longest Substring Without Repeating Characters
スライディングウィンドウ
文字列のs[left..right]をウィンドウとして保ち、その中の文字を集合に格納します。アクティブなウィンドウに同じUTF-16 charが重複して含まれないことが不変条件です。right位置の文字がすでに集合にある場合は、その重複文字がなくなるまで左端の文字を取り除き、leftを進めます。その後、新しい文字を追加し、最長の有効なウィンドウ長を更新します。
各反復の後、ウィンドウ内に重複はありません。現在の位置で終わる最長の部分文字列はleftより前から始められません。それより前から始めると重複文字が含まれるためです。したがって、現在のウィンドウ長を記録すれば、その位置で終わる有効な部分文字列の最長値を考慮できます。
Java実装
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.HashSet;
import java.util.Set;
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> window = new HashSet<>();
int left = 0;
int best = 0;
for (int right = 0; right < s.length(); right++) {
char current = s.charAt(right);
while (window.contains(current)) {
window.remove(s.charAt(left));
left++;
}
window.add(current);
best = Math.max(best, right - left + 1);
}
return best;
}
}
各文字はウィンドウに最大1回入り、最大1回出るため、時間計算量はO(N)です。集合に格納するのは入力中の異なる文字だけなので、LeetCodeの文字集合を前提とした追加領域はO(min(N, alphabet))です。