Python에서 문자 수가 k 이상인 가장 긴 부분 문자열의 길이를 찾는 프로그램

각 문자가 정렬된 문자열 s가 있고 숫자 k도 있다고 가정하면 모든 문자가 최소한 k번 발생하도록 가장 긴 부분 문자열의 길이를 찾아야 합니다.

따라서 입력이 s ="aabccddeeffghij" k =2와 같으면 여기서 가장 긴 부분 문자열이 "ccddeeff"이므로 출력은 8이 됩니다. 여기에서 모든 문자는 최소 2번 발생합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• rc() 함수를 정의합니다. 시간이 걸립니다
• c :=모든 문자와 해당 발생이 포함된 지도
• acc :=새 목록
• ans :=0
• 유효:=참
• lst의 각 x에 대해 다음을 수행합니다.
  • c[x]
  • 유효:=거짓
  • ans :=ans 및 rc(acc)의 최대값
  • acc :=새 목록
• 그렇지 않으면
  • acc 끝에 x 삽입

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

from collections import Counter
class Solution:
      def solve(self, s, k):
         def rc(lst):
            c = Counter(lst)
            acc = []
            ans = 0
            valid = True
            for x in lst:
               if c[x] < k:
                  valid = False
                  ans = max(ans, rc(acc))
                  acc = []
               else:
                  acc.append(x)
               if valid:
                  return len(acc)
               else:
                  ans = max(ans, rc(acc))
               return ans
            return rc(list(s))
ob = Solution()
s = "aabccddeeffghij"
k = 2
print(ob.solve(s, k))

입력

"aabccddeeffghij", 2

출력

8