https://leetcode.com/problems/longest-substring-without-repeating-characters/

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

겹치는 단어가 없는 substring의 최대 길이를 return 한다.

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

알파벳의 반복 없이 가장 긴 substring을 찾아야 한다.

hash 에 -1로 채워넣고 해봤다.

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int maxLength = 0;
		int curLength = 0;
		int begin = 0;
		int finish = 0;
		std::unordered_map<char, int> hash;
		for (int i = 0; i < s.size(); ++i)
			hash.emplace(s[i], -1);

		while (finish < s.size())
		{
			auto search = hash.find(s[finish]);
			if (search != hash.end())
			{				
				if (search->second == -1)
				{
					search->second = finish;
					curLength = finish - begin + 1;
					finish++;
				}
				else // 이미 한번 들렀으면
				{
					if (search->second >= begin) // 현재 가리키고 범위 안에서 겹친다.
					{
						begin = search->second + 1;
						search->second = finish;
						maxLength = std::max(maxLength, curLength);
						finish++;
					}
					else   // 겹치는게 있긴하나 현재 가리키고 있는 범위 안에는 없다.
					{
						search->second = finish;
						curLength = finish - begin + 1;
						maxLength = std::max(maxLength, curLength);
						finish++;
					}
				}
				
			}
		}
		return maxLength > curLength ? maxLength : curLength;
	}
};

Runtime: 16 ms, faster than 72.71% of C++ online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 11.1 MB, less than 26.66% of C++ online submissions for Longest Substring Without Repeating

Runtime: 28 ms, faster than 60.08% of C++ online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 10.9 MB, less than 27.37% of C++ online submissions for Longest Substring Without Repeating Characters.

공간적인 부분에서 많이 먹는다.

해쉬를 돌리면서 넣어주고 비교한다.

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int length = 0;
		int begin = 0;
		std::unordered_map<char, int> hash;
		for (size_t i = 0; i < s.size(); ++i)
		{
			if (hash.find(s[i]) != hash.end())
			{
				if(hash[s[i]] >= begin)  //  시작점을 바꿔줄 필요가 있을때만 바꿔준다.
					begin = hash[s[i]] + 1;
			}
			hash[s[i]] = i;
			length = std::max(length, int(i - begin + 1));
		}
		return length;
	}
};

Runtime: 20 ms, faster than 68.12% of C++ online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 8.4 MB, less than 73.21% of C++ online submissions for Longest Substring Without Repeating Characters.