[LeetCode] 3. Longest Substring Without Repeating Characters - Java

Longest Substring Without Repeating Characters - LeetCode

 

문제

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.

 

주어진 문자열에서 중복되지 않는 가장 긴 부분 문자열의 길이를 계산하는 문제이다.

 

---

 

내 풀이

class Solution {
    public int lengthOfLongestSubstring(String s) {

       int n = s.length();
        HashMap<Character, Integer> charIndex = new HashMap<>();
        int maxLength = 0;
        int left = 0;

        for (int right = 0; right < n; right++) {
            if (charIndex.containsKey(s.charAt(right)) && charIndex.get(s.charAt(right)) >= left) {
                left = charIndex.get(s.charAt(right)) + 1;
            }

            charIndex.put(s.charAt(right), right);
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;

    }
}

슬라이딩 윈도우와 해시 맵을 활용하여 풀이했다.

charIndex 맵은 문자와 해당 문자의 인덱스를 저장해서, 이미 나타난 문자의 위치를 기록하여 중복을 판단한다.

중복된 문자가 나타났을 때 그 문자의 left 가 그 문자의 인덱스보다 크거나 같으면 윈도우를 이동시키면서 최대길이를 업데이트한다.

 

• 시간복잡도 : O(n)
• 공간복잡도 : O(n)

 

---

 

다른 사람의 풀이

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLength = 0;

        int[] charIndex = new int[128];
        Arrays.fill(charIndex, -1);
        int left = 0;

        for (int right = 0; right < n; right++) {
            if (charIndex[s.charAt(right)] >= left) {
                left = charIndex[s.charAt(right)] + 1;
            }
            charIndex[s.charAt(right)] = right;
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

배열 charIndex를 사용하여 각 문자의 가장 최근 인덱스를 기록하고, 중복된 문자가 나타났을 때 윈도우를 조절한다

배열 charIndex는 문자 집합의 크기에 따라 128개의 항목을 가지고, 상수 크기의 공간이 사용된다.

따라사 공간 복잡도는 O(1)이다. (입력 크기에 관계없이 일정)

 

실제로 연산속도도 훨씬 빨랐다.