[LeetCode] LongestSubstring

문제

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

• Example 1:*

• Input:* "abcabcbb"

• Output:* 3

• Explanation:* The answer is "abc", with the length of 3.

  Example 2:

• Input:* "bbbbb"

• Output:* 1 Explanation: The answer is "b", with the length of 1.

  Example 3:

• Input:* "pwwkew"

• Output:* 3 Explanation: The answer is "wke", with the length of 3.

          Note that the answer must be a **substring**, `"pwke"` is a _subsequence_ and not a substring.

  문제풀이

• 시작점을 하나 정해서 중복된 것이 나올 때까지 순회 하는 식으로 하면 O(n제곱)

• 순회하면서 문자와 문자의 인덱스를 집어넣으면서 length++ 을 함.

• 순회하면서 중복이 나면, 그 때 중복이 난 것과의 diff 를 계산. diff 가 1 이라면 이전에 저장된 값들은 전부 쓸모가 없음. map.clear, length =1 로 초기화.

• diff 가 2 이상이라면, 중복이 된 값 사이의 문자열은 재활용 할 수가 있음. 단, 이전 값들은 쓸 수 없음.

왜 문제를 풀지 못했는가? 어떤 부분을 생각하지 못했는가?

• 중복이 됐을 때, 이전 값들을 쓸 수 없다는 것을 테스트케이스를 통해 알았음. 시간 많이 소요 됨.
• 또한, 중복이 됐을 때, 중복된 사이의 값들을 재활용하는 것을 생각하는 것도 시간 소요 됨.

Source