[leetcode] Longest Substring with At Least K Repeating Characters

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

Longest Substring with At Least K Repeating Characters - LeetCode

 

이론은 이해가 됐는데, 코드 작성이 어렵다. 알고리즘 강의를 하나 결제해서 들어야 하는걸까?

 

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is less than or equal to k.

 

아래는 leetcode에 있는 그림 설명이다. k보다 적은 횟수로 등장하는 문자열을 기준으로 문자를 양쪽으로 나누고 나뉘어진 문자열에 대해 재귀를 한다. 

이론을 보고 든 생각은 k보다 작은 문자의 idx를 찾아내고 해당 Idx가 만약 연속되는 경우에는 for문을 한번 더 돌려서 해당 문자가 끝나면 다시 후보지에 넣는식으로 하고싶었다.

디스커스를 보다가 내가 하고자했던 목적을 그대로 코드로 깔끔하게 옮겨적은 것을 찾았다.

leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/discuss/949622/Python-Short-recursion-20ms

def longestSubstring(self, s, k):
    def divide_and_conquer(s):
        char_freq = collections.Counter(s)
        for i, c in enumerate(s):
            if char_freq[c] < k:
                
                j = i + 1
                while j < len(s) - 1 and char_freq[s[j]] < k:
                    j += 1 #해당 문자가 끝날때까지 ++;
                    
                return max(divide_and_conquer(s[:i]), divide_and_conquer(s[j:])) #양쪽 값에 대해서 다시 재귀로 체크한다.
                     
        return len(s) #위 return 구문에서 max를 return하므로 최종 return은 최댓값이 된다.
              
    return divide_and_conquer(s)

그리고 좀 더 찾아보다가 

[LeetCode][Python3] 395. Longest Substring with At Least K Repeating Characters

굉장히 간결하게 잘 푸신 코드다. split()에 해당 값을 직접넣었다. 개인적으로 나는 위에 디스커스 코드가 더 이해가 잘되었다 😉