참고
문제해설
NOTE
•
입력값 ⇒ 문자열
•
출력값 ⇒ 문자열중 중복되지 않는 문자열 최대길이
문제 로직고민
NOTE
•
이전문제처럼 투포인터 방식을 사용한다.
◦
left, right를 0으로 초기화 한뒤, 다음 과정을 순회한다.
◦
이전에 있던 값이 아니다
▪
right를 증가시키고, 중복값을 체크할 구조에 문자를 넣는다.
◦
이전에 있던 값이다
▪
해당 중복값이 있던 idx만큼 left를 증가시킨다.
▪
단 중복값의 idx가 left보다 작다면, 갱신만하고, 넘어간다.
•
문자열을 순회하면서 이미 담겨있다는 정보를 어떻게 알아낼것인가?
◦
문자열의 중복여부와, 해당 idx를 가지고 있어야하므로 Map을 사용한다.
작성코드
NOTE
import java.util.*;
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap();
int left = 0;
int result = 0;
for(int right=0; right < s.length(); right++){
char temp = s.charAt(right);
// 아직 중복된 값이 없는 경우
if(!map.containsKey(temp)) {
map.put(temp, right);
result = Math.max(right - left + 1, result);
}
// 중복된 값이 있는 경우
else{
if(map.get(temp) >= left) left = map.get(temp) + 1;
else result = Math.max(right - left + 1, result);
map.put(temp, right);
}
}
return result;
}
}
Java
복사
정답코드
NOTE
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int maxLength = 0;
int[] charIndex = new int[128];
for (int i = 0, j = 0; j < n; j++) {
char currentChar = s.charAt(j);
if (charIndex[currentChar] > i) {
i = charIndex[currentChar];
}
maxLength = Math.max(maxLength, j - i + 1);
charIndex[currentChar] = j + 1;
}
return maxLength;
}
}
Java
복사
실행시간이 가장 짧은 코드
•
Map을 사용하지 않고, 크기 128의 char 배열로 idx를 체크하고 있다.
•
아스키코드가 128개의 문자로 이루어지므로 이를 응용한것 같다.
•
이외에는 큰 틀의 로직은 동일한것 같다.