[ Top Interview 150 ] 3. Longest Substring Without Repeating Characters

문제

3. Longest Substring Without Repeating Characters

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

 A substring is a contiguous non-empty sequence of characters within a string.

• Input : 문자열 s
• Output : s의 연속적인 일부분을 가져왔을 때, 내부에 중복되지 않는 문자열들 중 가장 긴 문자열의 길이

알고리즘 전략

• Sliding Window

  • 해당 문제는 1차원 데이터를 연속적인 구간으로 사용함
  • 구간이 움직이면서 추가/제거 되는 값에 따라 대상값(구간 내부 원소)이 규칙적으로 변화한다.
  • Sliding Window를 사용하기 적합하다.

• 알고리즘 전략 : Sliding Window + Set 자료구조 이용

  • 중복 원소가 있는지 빠르게 파악하기 위해 Set 자료구조를 사용

1차 답안

• Time complexity : O(n)
• Space complexity: O(n)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }

        Set<Character> charSet = new HashSet<>();

        int front = 0;
        int behind = 0;
        charSet.add(s.charAt(0));

        int maxLength = 1;
        while (behind < s.length() - 1) {
            behind++;
            char newChar = s.charAt(behind);

            if (!charSet.contains(newChar)) {
                charSet.add(newChar);
                maxLength = Math.max(behind - front + 1, maxLength);
                continue;
            }

            while (newChar != s.charAt(front)) {
                charSet.remove(s.charAt(front));
                front++;
            }
            front++;
        }

        return maxLength;
    }
}