C++でLeetCodeの「Longest Substring Without Repeating Characters」問題を解く
Problem
https://leetcode.com/problems/longest-substring-without-repeating-characters/
Answer
class Solution {
public:
int lengthOfLongestSubstring(std::string s) {
std::unordered_map<char, int> map;
int maxLength = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
if (map.find(s[right]) != map.end()) {
left = std::max(left, map[s[right]] + 1);
}
map[s[right]] = right;
maxLength = std::max(maxLength, right - left + 1);
}
return maxLength;
}
};
この問題の解答を考えてみよう。
入力がasapdaのとき、答えは4（sapd）である。
文字を先頭から見ていく。最初のa が現れたとき、最も長い部分文字列の長さは 1 (a) である。
次にsが初めて現れ、最も長い部分文字列の長さは2（as）に伸びる。
次はaが再び現れる。aはすでに文字列の最初に出現しているので、カウントに含めることはできない。
今回の目的は文字を繰り返さずに最も長い部分文字列の長さを見つけることである。つまり、asaは正解ではない。
次にsの位置から文字を数え始めなければならない。
これは、ある文字が再び出現した場合、その文字が最初に出現した文字の次の文字から数え始めなければならないことを意味する。
次にpが初めて出現し、最も長い部分文字列の長さが3（sap）に伸びる。
次にdも初めて出現し、最も長い部分文字列の長さを4（sapd）に伸ばす。
最後にaが再度現れるが、同じ文字はカウントに含まないので数えない。
つまり、答えは4 (sapd)である。
上記の解答をコードで考えてみよう。 重要な点はある文字が再び出現したとき、その文字が最後に出現したときの位置の次の文字から数え始める必要があるということです。
文字に出会ったときのindexを保存する。
例えばasapdaの場合、aはindexが0、sはindexが1である。
a が再び出現したときは、最初の a の次のインデックスから数え始め、新しい a のindexで a のindexを更新する必要がある。
同じ文字のindexを複数保存する必要はない。
Mapは一意なkeyとvalueのペアを格納できるので、この問題に適している。文字をkeyとして、そのindexをvalueとして格納する。
そして、2つの変数が必要になります。1番目の変数はカウントを開始する場所を示し、2番目の変数はカウントを終了する場所をします。 答えのコードを詳しく見てみよう。
std::unordered_map<char, int> map;
int maxLength = 0;
int left = 0;
mapはMapデータ構造として宣言し、文字をkey、そのindexをvalueとして格納する。
maxLength変数は最も長い部分文字列の長さを数え、left変数はどこからカウントを始めるかを示します。
for (int right = 0; right < s.length(); right++) {
変数 right は文字をカウントし終える位置を進める。
if (map.find(s[right]) != map.end()) {
left = std::max(left, map[s[right]] + 1);
}
同じ文字に再度出会ったら、カウントを開始する位置であるleftを更新する。
しかし、leftは現在の位置から戻ってはならない。leftを現在のleftと元のleftの大きい方に再割り当てする。
map[s[right]] = right;
maxLength = std::max(maxLength, right - left + 1);
}
map[s[right]] = right は文字をkeyとして、そのindexをvalueとして格納する。
std::max(maxLength, right - left + 1) は maxLength を現在の maxLength と right (カウント終了位置) から left (カウント開始位置) を引いた値の大きい方で更新する。
インデックスは0から始まるので、正確な文字カウントを保証するために1を加える。
