3.md

3. Longest Substring Without Repeating Characters

Solution 1

시간복잡도 : O(N^2)

문자열 탐색 loop : N

loop내에서 find() : N

N*N

알고리즘 : 완전 탐색

풀이 설명 :

1. queue에 입력된 문자열의 앞부터 순서대로 넣는다. set에도 해당 char를 저장한다.
2. 이전에 set에 들어있던, char가 다시 등장하면, queue에서 맨 앞 ~ 해당 중복된 char까지 pop한다. (pop할 때, set에서도 지워준다.)
3. 2가 끝난 후에 queue에 해당 char를 다시 넣는다.
4. 매 loop의 끝에서, 현재의 queue의 길이가 answer보다 길면 answer를 갱신한다.

• answer 초기값 : 0

• set에 원소의 개수가 0개일 때, find() 실행시 오류가 나므로, loop들어가기 전에 문자열의 0번째 원소를 넣고 시작한다

소스코드 :

#include <queue>
#include <set>
#include <string.h>
using namespace std;

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int answer = 0;
		queue<char> q;
        set<char> st;
		int count = 0;

		if (s[0] == ' ' || s.size() == 1)
			return 1;
        q.push(s[0]);
        st.insert(s[0]);
        for (int i=1;i<s.size();i++){
            if (st.find(s[i]) == st.end()){ //중복x
                q.push(s[i]);
                st.insert(s[i]);
            }
            else {
                while (q.front() != s[i]){
                    st.erase(st.find(q.front()));
                    q.pop();
                }
                q.pop();
                q.push(s[i]);
            }
            if (q.size() > answer)
                answer = q.size();
        }
		return answer;
	}
};