395. Longest Substring with At Least K Repeating Characters

문제

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

코드

못 풀어서 코드는 없다.

피드백

• 답지는 이거다. https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/discuss/170010/Java-O(n)-Solution-with-Detailed-Explanation-Sliding-Window

• 아이디어는 다음과 같다.

  • 바깥 for는 한 번에 수용할 알파벳 종류 개수를 제한한다.
  • 알파벳의 종류가 꽉 차지 않았다면 right로 이동한다.
    • 해당 알파벳을 count++한다.
    • 새로운 알파벳이 들어왔다면 알파벳 종류 수를 하나 더한다. (한 자리를 사용하게 됨)
    • 만약 K와 같다면 현재 K를 만족하는 알파벳 종류의 개수, kOrMore를 1 증가시킨다.
  • 알파벳의 종류가 초과 했다면 left를 이동하여 알파벳 종류 하나를 빼려고 해야한다.
    • 해당 알파벳을 count--한다.
    • 만약 알파벳종류 하나가 0이 되었다면, 슬롯을 내려논 것이므로 현재 알파벳 종류 수를 하나 뺀다.
    • K가 아니게 되었다면 kOrMore를 1 뺀다.
  • 만약 현재 알파벳 종류 슬롯이 꽉 차있고, K개를 만족하는 알파벳 종류 수가 현재 알파벳 종류 수와 같다면 left와 right를 통해 현재 String의 길이를 구하여 max를 갱신한다.

• 나는 생각도 못했다... 외우자.