Lognest Substring Without Repeating Characters
string s가 주어질때, 반복된 문자가 없는 가장 긴 부분문자열(substring)을 구하시오.
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Input
string s
Output
int
int answer
- 중복되는 문자를 없애는 것이 아닌 중복없는 부분중 가장 긴 부분을 추출하는 것이다.
- 영문자, 숫자, 기호, 공백이 포함된 s (아스키코드로 32 ~ 126번 안에 존재), chk
- 새로운 함수 cnt를 구현
: cnt(string s, int& from, vector<int> chk);
- 사용한 문자는 chk[s[i]] = i + 1을 통해 제외시키고, 나중에 제외시킨 문자가 등장했을때 함수를 종료시키면서 증가시킨 ans만큼 return;
- 이때, from에 chk[s[i]]를 저장해서 다음에 시작할 장소를 저장해둠.
- cnt함수가 끝날 때마다 return된 값을 answer와 비교하여 큰값을 저장
class Solution {
public:
bool exit = false;
int lengthOfLongestSubstring(string s) {
int answer = 0, from = 0;
vector<int> chk(128, 0);
while(!exit) {
int count = cnt(s, from, chk);
if(answer < count) answer = count;
}
return answer;
}
int cnt(const string s, int& from, vector<int> chk) {
int ans = 0;
for(int i = from; i < s.size(); i++) {
if(!chk[s[i]]) {
chk[s[i]] = i + 1; // 해당 문자가 있는 (위치 + 1) 저장
ans++;
}
else { // 종료
from = chk[s[i]];
return ans;
}
}
// 문자열의 마지막까지 돌았을 때
exit = true;
return ans;
}
};
결론 = 매우 좋지 못한 코드이다...
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int answer = 0, start = 0;
bool c = false;
vector<int> chk(128, 0);
for(int i = 0; i < s.size();) {
if(start > chk[s[i]] - 1) {
chk[s[i]] = i + 1; // 해당 문자가 있는 (위치 + 1) 저장
i++;
}
else {
if(answer < i - start) answer = i - start;
start = i = chk[s[i]];
c = true;
}
}
return answer;
}
};
Input : " " | Output : 0 | Expected : 1
else 를 거치지 않는 그대로가 답이 경우에 대한 예외가 빠짐
if(!c) answer = s.size();