while-loop O(N)
ch는 문자열 s의 idx번째에 있는 문자이고, sub_s는 s에서 pl번째 인덱스부터 (pr-1)번째 인덱스까지 자른 부분문자열이라고 하자. sub_s의 길이는 (pr-pl)이다. (부분문자열을 String 이나 char[] 에 담아놓지 않는다. )
- 문자열에 담긴 값들은 ASCII코드이므로 표현범위가 7-bit의 표현범위와 같다. (0~127)
- ch가 s의 부분문자열 sub_s 내에서의 존재여부를 판별할 방법으로 길이가 128인 배열을 사용하자.
- int[] exist , 인덱스는 문자 ch사용. exist[ch]로 ch가 sub_s에 존재하는지 그 여부와, s의 어느 인덱스에 있는지 알 수 있다.
- exist[ch]에 들어가는 값=idx+1
- ch가 s의 pr번째 인덱스의 문자일 때, ch를 sub_s에 포함할지 말지 결정하려고 한다. exist[ch]<=pl이면 sub_s에 ch가 존재하지 않기 때문에 ch를 포함한다. exist[ch]>pl이면 sub_s에 ch가 존재한다.
-
exist[ch]에 idx가 아닌 idx+1을 넣은 이유는 다음과 같다.
-
만약 exist[ch]=idx를 하면 어떻게 될까? int [] exist = new int[128]으로 인해 exist 배열의 원소의 초기값은 0이다. 그렇다면 임의의 ch에 대해 exist[ch]=0이므로 ch가 s의 0번째 인덱스에 위치해 있다는 것을 의미한다. int [] exist를 사용하기 전에 모든 요소의 값을 -1로 초기화해서 해결할 수도 있다. (조금 귀찮은 일이다.)
-
exist[ch]=idx+1을 하면 어떨까? 우선 exist배열을 사용하기 전에 -1로 초기화하는 작업을 생략할 수 있다. pl을 움직일 때 pl=exist[ch]이렇게 바로 대입한다. (그런데 exist배열을 사용할 때마다 헷갈린다. 귀찮더라도 위의 방법이 더 좋은 거 같다.)
-
경계조건: 모든 문제는 경계조건에 유의하여야 한다.
-
(1) 함수에서 사용한 변수들의 경계조건 pl==pr==0 :
-
(2) 함수에서 사용한 변수들의 경계조건 pr >= s_len : while 문의 조건 pr<s_len으로 s의 인덱스 범위에 벗어나서 요소를 접근하는 하는 경우를 예방하였다. while문이 끝나고 sub_s의 길이를 한 번 더 계산하여 max값을 갱신한다.
-
(3) 함수에서 사용한 변수들의 경계조건 exist.length == 128: String의 원소는 0~127까지의 값만 가지므로 exist[ch]에서 인덱스 에러가 발생할 일은 없다.
-
(4)함수에서 사용한 변수들의 경계조건 exist배열 요소의 값: 위에서 언급한 바와 같이 s의 하한경계인 0과 exist배열 요소의 초기값 0 이 혼동될 수 있어서 exist[ch]=idx+1로 설정하였다.
-
(5) 함수의 입력의 경계조건 s의 길이가 0: 함수에서 max=0, pl=pr=0으로 설정하여 빈 문자열 ""에서도 잘 동작한다.
-
(6) 함수 입력의 경계조건 s의 길이가 1 (s의 첫 인덱스==마지막 인덱스):
ch=s.charAt(pr) exist[ch]는 항상 pr보다 작거나 같은 값을 가진다. pl < exist[ch]<=pr 이면 sub_s에 ch가 존재한다는 의미이다.
소스코드 :
class Solution {
public int lengthOfLongestSubstring(String s) {
int max=0;
int []exist = new int[128];
int pl=0,pr=0;
int s_len=s.length();
int len;
char ch;
while(pr<s_len) {
ch= s.charAt(pr);
if(exist[ch]<=pl) { // ch dosesn't exist in sub_s
exist[ch]=++pr;
}else { // ch exists in sub_s
len = pr-pl;
max = (max>len)?max:len;
pl=exist[ch];
exist[ch]=++pr;
}
}
len = pr-pl; //calculate sub_s length which is located at the end of s
max=(max>len)?max:len;
return max;
}
}