[leetcode] Longest Substring Without Repeating Characters

medium 3. Longest Substring Without Repeating Characters

• 코드

  class Solution {
    public int lengthOfLongestSubstring(String str) {
        int inputLength = str.length();
        List<Character> nonRepeatedChars = new ArrayList<>();
        int count = 0, longestLength = 0;
  
        for (int i = 0; i < inputLength; i++) {
            char c = str.charAt(i);
            
            if (nonRepeatedChars.contains(c)) {
                // c의 위치(loc) 전까지 모두 삭제
                int loc = nonRepeatedChars.indexOf(c);
                for (int i = 0; i < loc; i++) {
                    nonRepeatedChars.remove(0);
                }
                if (loc >= 0) {
                    nonRepeatedChars.subList(0, loc + 1).clear();
                }
  
                // c 추가
                nonRepeatedChars.add(c);
                
                count = nonRepeatedChars.size();
                continue;
            }
  
            nonRepeatedChars.add(c);
            count++;
            if (count > longestLength) {
                longestLength = count;
            }
        }
  
        return longestLength;
    }
  }

  • Runtime: 6ms, Memory: 38.9MB

풀이

1. 입력받은 str을 한 글자씩 순회하면서 List<Character>에 순서대로 넣는다.
2. List<Character>에 이미 있는 글자이면 첫번째 글자부터 이미 들어있던 위치까지의 글자를 리스트에서 삭제한다.
3. 리스트에 존재하지 않던 글자이면 리스트의 마지막에 추가한다.
4. 1~3을 수행하면서 리스트의 최대 길이를 센다.