LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 문자열 s
2. output: 주어진 문자열에서 같은 글자가 없는 연속된 최대 길이 리턴
   • 0 <= s.length <= 5 * 104
   • s consists of English letters, digits, symbols and spaces.

Idea

Hash에 문자가 등장한 idx를 저장하여 이미 값이 저장되어 있는 경우(중복 출현) Substring의 시작 idx를 이미 저장된(중복 문자가 처음으로 등장한) idx+1로 조정하는 식으로 코드를 작성했다.

하지만 abcba 와 같은 테스트 케이스에서, Substring의 시작 idx가 2에서 1로 작아지는 상황이 발생하므로 시작 idx를 현재 Substring의 시작 idx와 중복 문자의 idx+1 중 큰 값으로 조정하도록 하였다.

Solution

1. hash를 통해 문자가 나타난 인덱스 표시 ⭕

   앞에서 부터 순서대로 문자의 인덱스를 hash에 저장 → hash[문자] = 인덱스

   중복되는 문자가 나나탄다면 시작 인덱스를 조정

   → max(중복되는 첫 문자의 idx + 1 or 현재 시작 idx)

   최대 길이로 answer 갱신

   class Solution {
       fun lengthOfLongestSubstring(s: String): Int {
           var answer = 0
           val repeating = mutableMapOf<Char, Int>()
           var startIdx = 0 // 찾는 문자열의 시작 idx
           for (idx in s.indices) {
               val c = s[idx]
               if (repeating.containsKey(c)) { // 재등장한 문자인 경우
                   // 현재 시작idx와 반복되는 문자의 첫 idx중 큰값으로 시작 idx 조정
                   startIdx = Math.max(repeating[c]!! + 1, startIdx)
               }
               repeating[c] = idx // 문자의 현재 idx 저장
               // 최대 길이 갱신
               answer = Math.max(answer, idx - startIdx + 1)
           }
           return answer
       }
   }
   

   시간 복잡도: 문자 순회 = n

   

Point

1. Substring의 시작 인덱스를 max(원래 시작 idx, 중복 문자의 첫 등장 idx)로 조정하는 것이 중요