はじめに

---

与えられたsの内部で、文字が重複しない最大のsubstringを探し、その長さを求める問題．

スライディングウィンドウとハッシュテーブルを活用して解いた。

コード全体

---

int lengthOfLongestSubstring(string s) {
  int maxLength = 0;
  map<char,int> chars;
  for(size_t left=0, right=0; right<s.length(); right++){
    chars[s[right]]++;
    while(left<right && chars[s[right]]>1) chars[s[left++]]--;
    if( maxLength < right-left+1 ) maxLength = right-left+1;
  }
  return maxLength;
}

解説

---

maxLengthは、最大長を格納して更新していく。 charsは、各文字がsubstringに何個含まれているかを記憶する。

int lengthOfLongestSubstring(string s) {
  int maxLength = 0;
  map<char,int> chars;

leftはsubstringの左端を、rightは、substringの右端のインデックス番号を指す。 rightを更新するごとにcharsに含有文字数を足していく。

  for(size_t left=0, right=0; right<s.length(); right++){
    chars[s[right]]++;

rightの文字が重複している場合、重複が解消されるまでleftを動かす。

    while(left<right && chars[s[right]]>1) chars[s[left++]]--;

left・rightに対するsubstringの長さはright-left+1であり、maxLengthを更新する。

    if( maxLength < right-left+1 ) maxLength = right-left+1;
  }

maxLengthを返す。

  return maxLength;
}