数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 Python 中查找给定字符串中具有 k 个唯一字符的最长子字符串
假设我们有一个字符串，我们必须返回具有恰好 k 个唯一字符的最长可能的子字符串，如果有多个最长可能长度的子字符串，则返回其中任何一个。
因此，如果输入类似于 s = "ppqprqtqtqt"，k = 3，则输出将为 rqtqtqt，因为它的长度为 7。
为了解决这个问题，我们将遵循以下步骤：
N := 26
定义一个函数 is_ok()。这将接收 count 和 k 作为参数。
val := 0
对于 i 从 0 到 N，执行以下操作：
如果 count[i] > 0，则
val := val + 1
当 (k >= val) 时返回 true
从主方法中，执行以下操作：
unique := 0，size := s 的大小
count := 一个大小为 N 的数组，用 0 填充
对于 i 从 0 到 size，执行以下操作：
如果 s[i] 的计数为 0，则
unique := unique + 1
将 s[i] 的计数增加 1
如果 unique < k，则
没有这样的字符，退出
start := 0，end := 0
window_length := 1，window_start := 0
count := 一个大小为 N 的数组，用 0 填充
将 s[0] 的计数增加 1
对于 i 从 1 到 size，执行以下操作：
将 s[i] 的计数增加 1
end := end + 1
当 is_ok(count, k) 为假时，执行以下操作：
将 s[i] 的计数减少 1
start := start + 1
如果 end-start+1 > window_length，则
window_length := end-start+1
window_start := start
返回 s 的子字符串（从索引 window_start 到 window_start + window_length）
示例
让我们看看以下实现以获得更好的理解：
N = 26
def is_ok(count, k):
val = 0
for i in range(N):
if count[i] > 0:
val += 1
return (k >= val)
def k_unique_chars(s, k):
unique = 0
size = len(s)
count = [0] * N
for i in range(size):
if count[ord(s[i])-ord('a')] == 0:
unique += 1
count[ord(s[i])-ord('a')] += 1
if unique < k:
return "Not sufficient characters"
start = 0
end = 0
window_length = 1
window_start = 0
count = [0] * len(count)
count[ord(s[0])-ord('a')] += 1
for i in range(1,size):
count[ord(s[i])-ord('a')] += 1
end+=1
while not is_ok(count, k):
count[ord(s[start])-ord('a')] -= 1
start += 1
if end-start+1 > window_length:
window_length = end-start+1
window_start = start
return s[window_start:window_start + window_length]
s = "ppqprqtqtqt"
k = 3
print(k_unique_chars(s, k))输入
"ppqprqtqtqt", 3
输出
rqtqtqt
547 次浏览
