3. Longest Substring Without Repeating Characters 수정

문제

Given a string s, find the length of the longest substring without repeating characters.

 

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

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.

 

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

 

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

 

 

풀이

이전에는 String에 넣고, 중복된 문자가 있는 경우 다시 시작했던 index의 다음부터 다시 비교하다 보니 시간과 메모리 소요가 컸다.

최대한 반복하지 않고, 변수도 줄일 생각으로 문제를 다시 한번 풀어보았다.

이번에는, 가면서 중복된 문자가 있을 경우 start를 1증가시켜서 다시 비교해 나가는 방식으로 코드를 작성했다.

substring을 사용하여 현재 index의 문자가 없는 부분까지 start를 증가시킨 후, 다음 index부터 비교하도록 하여 반복 시간과 메모리 사용량을 줄였다.

 

 

코드

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int start = 0;
        int idx = 0;
        int maxlength = 0;
        
        while(idx < s.length()) {
        	if(start > idx) {
        		break;
        	}
        	
        	if(!s.substring(start, idx).contains(""+s.charAt(idx))) {
        		idx++;
        		maxlength = (maxlength - (idx - start) > 0) ? maxlength : (idx - start);
        		continue;
        	}
        	
        	start++;
        }
        
        return maxlength;
    }
}

 

 

결과

• AS-IS

Runtime: 534 ms, faster than 5.01% of Java online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 141.3 MB, less than 5.06% of Java online submissions for Longest Substring Without Repeating Characters.

 

• TO-BE

Runtime: 13 ms, faster than 40.04% of Java online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 40 MB, less than 49.03% of Java online submissions for Longest Substring Without Repeating Characters.