# LeetCode 395. Longest Substring with At Least K

## Description

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3
Output:
3
The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2
Output:
5
The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

## 描述

输入:
s = "aaabb", k = 3

3

输入:
s = "ababbc", k = 2

5

### 思路

• 统计每个字符出现的次数，用次数少于 k 的字符对原字符串进行拆分。递归地对字符串进行同样的操作。
• 在字符串中出现次数少于 k 的字符，一定不能在最长字符串里面，所以用此字符串对原字符串进行切割。如果所有的字符串出现的此处都大于 k，则返回字符串的长度。

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-08-27 21:07:09
from collections import Counter
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
for key, v in Counter(s).items():
if v < k:
return max(self.longestSubstring(sub, k) for sub in s.split(key))
return len(s)

|
9月前
Leetcode 516. Longest Palindromic Subsequence

32 0
|
9月前
|
Java
Leetcode 3. Longest Substring Without Repeating Characters

36 3
LeetCode contest 187 1437. 是否所有 1 都至少相隔 k 个元素 Check If All 1's Are at Least Length K Places Away
LeetCode contest 187 1437. 是否所有 1 都至少相隔 k 个元素 Check If All 1's Are at Least Length K Places Away
95 0
LeetCode Contest 178-1368. 使网格图至少有一条有效路径的最小代价 Minimum Cost to Make at Least One Valid Path in a Grid
LeetCode Contest 178-1368. 使网格图至少有一条有效路径的最小代价 Minimum Cost to Make at Least One Valid Path in a Grid
96 0
LeetCode 424. Longest Repeating Character Replacem

87 0
LeetCode 409. Longest Palindrome

62 0
|
1天前
|
Python
【Leetcode刷题Python】77. 组合
LeetCode题目77的两种Python编程解决方案，题目要求给定两个整数n和k，返回范围[1, n]中所有可能的k个数的组合。
10 3
|
1天前
|
Python
【Leetcode刷题Python】131. 分割回文串
LeetCode题目131的Python编程解决方案，题目要求将给定字符串分割成所有可能的子串，且每个子串都是回文串，并返回所有可能的分割方案。
8 2
|
1天前
|

【Leetcode刷题Python】216. 组合总和 III
LeetCode题目216的Python编程解决方案，题目要求找出所有和为n的k个数的组合，条件是只能使用数字1到9，每个数字最多使用一次，且解集中不能包含重复的组合。
9 2
|
1天前
|
Python
【Leetcode刷题Python】473. 火柴拼正方形
LeetCode题目473的Python编程解决方案，题目要求使用给定长度的火柴棒拼成一个正方形，不能折断火柴棒且每根火柴棒必须使用一次，判断是否能拼成正方形。
8 2