중복되지 않는 가장 긴 Substring 구하기
알 - 하 ! (알고리즘 하이 라는 뜻)
오늘 풀어볼 문제는 "중복되지 않는 가장 긴 Substring 구하기" 이다.
(link : leetcode.com/problems/longest-substring-without-repeating-characters/)
문제 설명을 간략하게 하자면, 문자열이 주어진다. 이 때, 문자열엔 알파벳, 숫자, symbols, space가 들어 갈 수 있다고한다.
이때 중복되지 않으면서 이어지는 가장 긴 문자열의 길이를 구하는게 문제이다.
이렇게 설명하면 좀 어려울 수 있으니, 간단하게 설명하면, String : "pwwkew" 일때, 중복없이 가장 긴 substring은 "wke"가 된다.
사실 처음에 봤을때 굉장히 쉬운 문제인줄 알았으나,,, 생각보다 까다로운 문제였다 .. (아님 내가 잘못하는거이거나)
다양한 방법이 있을 수 있겠으나, 나는 sliding window를 상상하며 풀었다.
문제 풀이 방법은 다음과 같다.
[0] 각각의 알파벳, 숫자, symbols, space에 대하여 현재 substring sliding window에 포함되어있는지 아닌지를 저장할 길이 256짜리 배열을 만든다. (알파벳, 숫자, symbols, space가 char형으로 표현할 수 있는 모든 값이며 char의 크기는 1byte(2^8 == 256)이다.
[1] window의 right가 가리키는 값(window에 다음으로 들어올 char)이 현재 윈도우에 존재하는지 체크한다.
[2-1] 만약, window에 right가 가리키는 값이 존재하지 않는다면, window에 해당 char을 포함시킨다. 단, 위에서 생성한 길이256짜리 배열에 해당 char를 포함하고 있다고 표시하는것도 잊지 말자!
window사이즈가 늘어났기 때문에, 최대값에 대한 비교도 잊지말자 !
[2-2] 만약, window에 right가 가리키는 값이 존재한다면, window의 가장 좌측에 위치한 원소를 window에서 제거한다.
이러한 과정을 통해서, loop가 다시 돌았을때, right가 가리키는 값을 window에 다시 넣을 수 있게 된다.
[3] 만약 right가 주어진 문자열의 끝까지 포함했다면 프로그램을 종료하고, max 값을 return 한다.
사실, 이 문제는 글로 쓰는 것보다 그림 설명이 이해가 빠르다.
▶ 이 문제의 핵심은, [1]현재 window에 right가 가리키는 값이 있는지 여부를 배열을 이용해 O(1)로 찾는 것과(혹은 hash도 이용할 수 있을듯), [2] left, right를 이용해 window를 움직이는 과정이 가장 중요하다고 생각한다.
package com.algoFactory.leetcode;
/**
* User: Minwoo Kang
* Date: 2020/10/29
* Time: 12:38 AM
*/
public class LongestSubstring {
public int lengthOfLongestSubstring(String s) {
int[] including = new int[256];
// if including['a'] != 1, 'a' is in current substring window
// if including['a'] ==0, 'a' is not in current substring window
int max = 0;
int left = 0;
int right = 0;
int length = s.length();
if (s.length() == 1)
return 1;
while (left < length) {
if (including[s.charAt(right)] == 0) {
including[s.charAt(right)]++;
right++;
max = Math.max(max, right - left);
if (right == length) {
break;
}
} else {
including[s.charAt(left)]--;
left++;
}
}
return max;
}
}
github link : github.com/Minwoo-Kang/allOfalgorithm/blob/master/src/com/algoFactory/leetcode/LongestSubstring.java