문제

Longest Substring Without Repeating Characters - LeetCode

Code

1차풀이

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

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

        int left = 0;
        int right = 0;
        int answer = 0;
        characterSet.add(s.charAt(left));

        while (right < s.length()){
            if (left == right || !characterSet.contains(s.charAt(right))){
                characterSet.add(s.charAt(right));
                answer = Math.max(characterSet.size(), answer);
                right += 1;

            } else{
                while (s.charAt(left) != s.charAt(right)) {
                    characterSet.remove(s.charAt(left));
                    left += 1;
                }
                if (left < right) {
                    characterSet.remove(s.charAt(left));
                    left += 1;
                }
            }
        }

        return answer;
    }
}

• 투 포인터를 이용하여 문제를 해결하였다.
• left == right || !characterSet.contains(s.charAt(right))
  • left = right이거나 중복되는 char가 없을 때 characterSet, answer를 업데이트하고 right를 한칸 움직였다.
• while (s.charAt(left) != s.charAt(right))
  • right 위치의 char가 중복인 경우 현재의 right 위치의 char와 중복될 때까지 left를 이동시켰다.
  • 이후 left 위치의 char와 right 위치의 char가 서로 같지만 left, right가 다른 경우 한 칸 더 이동시켰다.

속도는 전반적으로 무난했으나 풀이가 명확하지 않다.

2차 풀이

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

        Map<Character, Integer> characterMap = new HashMap<>();

        int left = 0;
        int right = 0;
        int answer = 0;
        characterMap.put(s.charAt(left), 1);

        while (right < s.length()){
            System.out.println("left: " + left + " right: " + right);
            if (left == right || !characterMap.containsKey(s.charAt(right))){
                characterMap.put(s.charAt(right), 1);
                answer = Math.max(right - left + 1, answer);
                right += 1;

            } else{
                while (s.charAt(left) != s.charAt(right)) {
                    characterMap.remove(s.charAt(left));
                    left += 1;
                }
                if (left < right) {
                    characterMap.remove(s.charAt(left));
                    left += 1;
                }
            }
        }
        return answer;
    }
}

Set이 아닌 Map을 사용하여 key를 통한 접근을 시도하였으나 큰 차이는 없다.

다른 풀이

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> used = new HashMap<>();

        int answer = 0;
        int left = 0;
        int right = 0;

        for (char c: s.toCharArray()){
            if (used.containsKey(c) && left <= used.get(c)){
                left = used.get(c) + 1;
            } else {
                answer = Math.max(answer, right - left + 1);
            }

            used.put(c, right);
            right += 1;
        }

        return answer;
    }
}

• right는 계속해서 마지막 글자를 가리키고, left를 조건에 맞추어 움직이면서 데이터를 업데이트하였다.
• 해시 맵에 해당 글자가 마지막으로 나온 위치를 저장한다. 이를 통해 새롭게 들어온 문자가 등장했었던 문자라면 해당 문자의 마지막 위치 + 1로 이동한다.