Description

Given a string, find the length of the longest substring without repeating characters.

Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

来源：LeetCode 03 Longest Substring Without Repeating Characters

Solution

好久没刷算法题了，手有点生，没有什么思路，下面的答案是看过提示之后才写出来的。

Approach 1 暴力解法

将所有的子串都穷举出来，并对它们进行判断，就能够得到最长子串的长度。这个算法很显然需要耗费很长时间。
需要注意的是： C++20中才支持 std::set::contains 这个接口（根据cppreference.com）。

bool isStringWithUniqueString(const string& str)
{
    // 用于判断字符串是否是具有唯一字符的
    set<char> setChar;
    for (size_t i = 0; i<str.length(); ++i)
    {
	if (setChar.find(str[i]) != setChar.end())
	{
	    return false;
	}

	setChar.insert(str[i]);
    }
    return true;
}

int lengthOfLongestSubstring(string s)
{
    int lengthMax = 0;

    for (size_t i=0; i<s.length(); ++i)
    {
	for (size_t j=i+1; j<=s.length(); ++j)
	{
	    // get sub-string
	    string strTemp = s.substr(i, j-i);
	    if (isStringWithUniqueString(strTemp))
	    {
		lengthMax = max(lengthMax, (int)strTemp.length());
	    }
	}
    }

    return lengthMax;
}

Approach 2 滑动窗口

滑动窗口的概念在字符串处理问题中十分常用，保持子串的左端点不动，不断拓展右侧端点，就能穷举出所有满足条件的子串。
需要注意的是这句话： lengthMax = max(lengthMax, int(j-i+1));

  1. std::max 并不能同时匹配 int 和 size_t ，所以需要进行强制类型转换。
  2. 在完成第 j 个字母的验证后，说明包含该字母的子串也满足条件，所以要进行 +1 操作，这个主要是针对只有一个字母的字符串。
int lengthOfLongestSubstring(string s)
{
    int lengthMax = 0;

    for (size_t i=0; i<s.length(); ++i)
    {
	// 这个循环目的是，验证从i到j的字符串是否满足条件
	set<char> setChar;

	for (size_t j=i; j<s.length(); ++j)
	{
	    char ch = s[j];
	    if (setChar.find(ch) != setChar.end())
	    {
		break;
	    }
	    else
	    {
		lengthMax = max(lengthMax, int(j - i + 1));
	    }

	    setChar.insert(ch);
	}
    }

    return lengthMax;
}

Approach 3 优化的滑动窗口

使用 map 对字母出现的位置进行记录，这样在出现相同字母时，就能够从上一次出现的位置向后开始寻找。
需要注意句话 it->second+1>=i , 需要对位置加1后再比较，这样才能保证 i 的坐标计算正确。

int lengthOfLongestSubstring(string s)
{
    int lengthMax = 0;

    map<char, size_t> mapPos;

    for (size_t i=0, j=0; j<s.length(); ++j)
    {
	char ch = s[j];
	map<char, size_t>::iterator it = mapPos.find(ch);
	if (it != mapPos.end())
	{
	    // 这里说明找到了字符上一次出现的位置
	    if (it->second + 1>= i)
	    {
		i = it->second + 1;
	    }
	}

	lengthMax = max(lengthMax, int(j - i + 1));

	mapPos[ch] = j;
    }

    return lengthMax;
}