Skip to content

Latest commit

 

History

History
11 lines (11 loc) · 623 Bytes

note0395.md

File metadata and controls

11 lines (11 loc) · 623 Bytes
Raw

Leetcode 395. Longest Substring with At Least K Repeating Characters

  • Type: Array, Divide and conquer
  • Approach:
    1. For an index range of start to end, we can calculate the frequency of each character.
    2. Then we scan from start to end, find the first character whose frequency is less than k, marked as mid.
    3. And find the next index whose frequency is larger than k, marked as nextMid.
    4. For now, we have two ranges which are [start, mid], [nextMid, end].
    5. Do the recursion.
  • Complexity:
    • Time: O(n^2)
    • Space: O(n)