[리트코드 / LeetCode] 3. Longest Substring Without Repeating Characters 풀이 - C++

문제 원문

Given a string s, find the length of the longest substring without repeating characters.
 
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:
   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.
Example 4:
   Input: s = "" Output: 0
 
Constraints:
   0 <= s.length <= 5 * 104s consists of English letters, digits, symbols and spaces.

코드 원문

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
    }
};

풀이

아직 많이 부족해서 그런지 이번 문제도 쉽지 않았네요

문제를 이해하는 것부터 문제였습니다.

중복된 문자가 나올 때까지의 문자열 중 가장 긴 문자열의 길이를 리턴하는 문제입니다.

문자열의 크기 만큼 순회하면서 중복되지 않은 문자는 추가하고

중복되는 문자가 나왔을 때 최댓값을 갱신하고 중복이 나온 문자만큼 삭제해 줍니다.

처음엔 그냥 vector를 초기화했었는데 그러니깐 중복된 문자의 위치에 따라 예외적인 상황이 나오게 되네요

어찌 보면 당연한 거였는데 아직 많이 부족한 것 같습니다.

순회를 마치고 vector에 저장된 값 마저 처리한 후 리턴해 줍니다.

성공 코드

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    vector<char> Words;
	int nMax = 0;

	for (int i = 0; i < s.size(); i++)
	{
    	//진행한 문자 중 중복된 값이 있는지 확인
		vector<char>::iterator iter = find(Words.begin(), Words.end(), s[i]);

		if (iter != Words.end())		// 있으면 nMax 갱신 및 문자열 제거
		{
			if (nMax < Words.size())	nMax = Words.size();
			Words.erase(Words.begin(), ++iter);	// 제거는 중복된 문자까지
			Words.push_back(s[i]);
		}
		else
		{
			Words.push_back(s[i]);		// 중복되지 않았으면 문자 추가
		}
	}
	if (nMax < Words.size())	nMax = Words.size();	// 문자열을 모두 탐색한 후 nMax 갱신

	return nMax;
    }
    
};

결과

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

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