[LeetCode] 3번: Longest Substring Without Repeating Characters

문제링크 : https://leetcode.com/problems/longest-substring-without-repeating-characters/

 

문제풀이

중복되는 문자를 포함하지 않는, 가장 긴 구간을 찾는 문제이다.

 

방법1)

입력된 문자의 처음부터 끝까지 중복되지 않는 모든 경우를 찾는다.

가장 단순한 방법이지만, 이렇게 풀면 n까지 for문을 두 번 돌게 되므로 O(n2)의 시간복잡도가 나온다.

방법2)

투 포인터 알고리즘을 사용한 방법이다.

투 포인터 알고리즘은 인덱스를 가리키는 두 개의 포인터를 이동시키는 방법이다.

포인터 i, j가 있다고 하면,

조건에 일치하는 경우 j 포인터 이동, 일치하지 않는 경우 i 포인터를 이동시킨다.

 

 

Set은 중복을 허락하지 않는 자료구조이다.

Set에 값을 add할 때 동일한 값이 이미 존재하면 false를 반환하고 add하지 않는다.

이를 이용해 문자열을 하나씩 Set에 추가한다.

동일한 문자가 이미 추가된 경우, 동일한 문자가 존재하지 않을 때까지 Set에 추가된 데이터를 순서대로 삭제한다.

 

 

소스코드

// Runtime: 8 ms, faster than 68.16% of Java online submissions for Longest Substring Without Repeating Characters.
// Memory Usage: 36.9 MB, less than 99.79% of Java online submissions for Longest Substring Without Repeating Characters.
public static int lengthOfLongestSubstring(String s) {
	Set<Character> subString = new HashSet<Character>();
	
	int max = 0;
	int i = 0;
	int j = 0;
	
	while (j < s.length()) {
		char c = s.charAt(j++);
		if (subString.add(c)) {
			if (max < j - i) max = j - i;
		}
		else {
			while (!subString.add(c)) {
				subString.remove(s.charAt(i++));
			}
		}
	}
	
	return max;
}

// Runtime: 103 ms, faster than 8.85% of Java online submissions for Longest Substring Without Repeating Characters.
// Memory Usage: 38.3 MB, less than 56.95% of Java online submissions for Longest Substring Without Repeating Characters.
//public static int lengthOfLongestSubstring(String s) {
//	int max = 0;
//	String newString = "";
//	for (int i = 0; i < s.length(); i++) {
//		for (int j = i; j < s.length(); j++) {
//			String c = s.charAt(j) + "";
//			if (newString.contains(c)) break;
//	   
//			newString += c;
//		}
//		
//		if (max < newString.length()) max = newString.length();
//		
//		newString = "";
//   }
//	
//	return max;
//}