LeetCode 3번 Longest Substring Without Repeating Characters

---

문제 링크

Longest Substring Without Repeating Characters - LeetCode

---

문제

Example 1:

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

Example 2:

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

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

---

풀이

이 문제는 주어진 문자열에서 문자를 중복하여 사용하지 않고 가장 긴 문자열의 길이를 리턴하는 문제입니다.

class Solution {
public:
	int lengthOfLongestSubstring(string s)
	{
		map<char, int> dict;
		int maxLen = 0, begin = 0;
		char key;

		for (int i = 0; i < s.size(); i++)
		{
			key = s[i];

			// 현재 노드 안에 있고, 시작 지점이 현재 중복되는 노드보다 앞에 있을 경우
			if (dict.find(key) != dict.end() && dict[key] >= begin)
			{
				maxLen = max(maxLen, i - begin);
				begin = dict[key] + 1;
			}

			dict[key] = i;
		}
		return max(maxLen, (int)s.size() - begin);
	}
};

Time Submitted	Status	RunTime	Memory
07/25/2021 19:21	Accepted	16 ms	8.5 MB

시간 복잡도 : O(N)