[LeetCode] Longest Substring Without Repeating Characters2️⃣
[LeetCode] Longest Substring Without Repeating Characters
Longest Substring Without Repeating Characters - LeetCode
문자열 s가 주어졌을 때, 반복되는 character가 없는 가장 긴 부분문자열의 길이를 구하라
문제 이해하기
- 정답은 substring이어야 한다. subsequence는 substring이 아님
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.
문제 해결하기 : 슬라이딩 윈도우 ( 투 포인터 )
- susbsequence가 아닌 substring이어야 한다고 했기 때문에 , 슬라이딩 윈도우로도 풀 수 있을 거라는 생각이 들었다.
- 가장 먼저 드는 생각은 역시, sliding window 다
- start, end라는 두개의 포인터를 사용한다. string상의 index를 가리키는 포인터다
- 이 문제의 경우 O(n)으로 문제를 풀 수 있어 진다.
- start = end = 0 에서 부터 시작하여, end를 increment 시킨다.
- 이미 등장했던 character를 가리키게 된 경우, 더이상 repeated character가 없을 때 까지 start를 움직인다.
- 이미 등장했던 character를 가리키게 된 경우에만, max값을 update한다
- 이미 등장했던 character를 가리키게 된 경우에만 max값을 update하다보면 , 이 경우를 지나치게 된다.
abcbdcaeg
012345678end가 index 3 이 될 때 repeated character가 등장한다.
-
max를 : end(3)-start(0) = 3 으로 업데이트 한다.
-
start를 2 로 움직인다. ( s.charAt(start) == s.charAt(cur즉 end) 일 때 까지 이동)
- 움직이는 동안 start 위치에 있던 것들은 visit[s.charAt(start)] = false로 업데이트한다
-
visit[s.charAt(end)] = true 로 업데이트한다.
end가 index 5 이 될 때 repeated character가 등장한다.
-
max를 : end(5)-start(2) = 3 으로 업데이트 한다.
-
start를 5 로 움직인다.( s.charAt(start) == s.charAt(cur즉 end) 일 때 까지 이동)
- 움직이는 동안 start 위치에 있던 것들은 visit[s.charAt(start)] = false로 업데이트한다
-
visit[s.charAt(end)] = true 로 업데이트한다.
그리고는 end는 ++ 를 하다보면 -> end는 9, start는 5인 상태에서 끝난다.
하지만 repeated character가 등장할 때만 max를 업데이트 하도록 했기에
실제, 이 string s의 접미사 [ 5 ... ] 가 longest substring임에도 max 업데이트되지 않음
따라서 for문 이 끝난 이후, 다시 한번 max를 업데이트한다
-
class Solution {
/*
ascii는 1byte를 사용하여 나타낼 수 있는 문자들에 대한 것
128bit
영문자, symbol, space를 나타낼 수 있음
*/
public boolean[] visit = new boolean[1000];
public int lengthOfLongestSubstring(String s) {
int ans = sliding(s);
return ans;
}
public int sliding(String s){
int start=0, end=0,len = s.length();
int cur = 0;
int max = 0;
// System.out.println(len);
for(; end<len; end++){
cur = s.charAt(end)-0;
if(visit[cur]){
// repeated character인 경우
// 1. 길이를 저장
max = Math.max(max,end-start);
// System.out.println("start :"+start+", end : "+end+", max : "+max);
// 2. window를 오른쪽으로 이동
while(start<end){
visit[s.charAt(start)-0] = false;
if(s.charAt(start) == s.charAt(end)){
start++;
break;
}
start++;
}
}
visit[cur] = true;
}
// end가 끝까지 간 경우 -> max를 update하는 로직이 실행되지 않는다.
// 즉, 접미사인 부분수열이 가장 긴 경우, for문에서는 탐색되지 않는다.
// 따라서 마지막에 이렇게, end-start 가 max일 수도 있기 때문에 이를 확인해 준다
max = Math.max(max,end-start);
// System.out.println("start :"+start+", end : "+end+", max : "+max);
return max;
}
}
Author And Source
이 문제에 관하여([LeetCode] Longest Substring Without Repeating Characters2️⃣), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ynoolee/LeetCode-Longest-Substring-Without-Repeating-Characters2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)