-
99% Javascript Solution with Explanation - LeetCode Discuss
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문자를 k회 바꿀 수 있을 때, 같은 문자로 이루어진 문자열 길이가 최대가 되는 경우
길이가 최대인 Subarray를 찾고, maxLength = Math.max(maxLength, Subarray.length); 식으로 계속해서 업데이트하는게 아님. 비슷한 생각을 갖는 분의 댓글을 하나 퍼오자면
Java 12 lines O(n) sliding window solution with explanation - LeetCode Discuss
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
This solution is great, best so far. However, it requires a bit more explanation.
Since we are only interested in the longest valid substring, our sliding windows need not shrink, even if a window may cover an invalid substring. We either grow the window by appending one char on the right, or shift the whole window to the right by one. And we only grow the window when the count of the new char exceeds the historical max count (from a previous window that covers a valid substring).
That is, we do not need the accurate max count of the current window; we only care if the max count exceeds the historical max count; and that can only happen because of the new char.
Here's my implementation that's a bit shorter
가령, s = "ABCBDAQ", k = 2인 경우, ABCB나 BCBD가 된 경우 Math.max를 돌리는게 아님. 그도 그럴 것이 최종적으로 return할때 right와 left는 BDAQ 문자열을 가리키고 있음.
근데 사실상 내가 문제를 풀만한 지식을 갖고 있었다면 위 주소의 글쓴이 처럼 Math.max로 계속 업데이트했을 듯... 댓글처럼 문제 풀이를 생각하기는 쉽지 않을 것 같다.
댓글
