Python: substrings de tamaño N con caracteres distintos K

Dada una string, la tarea es escribir un programa de Python para extraer strings de tamaño N y tener K caracteres distintos.

Ejemplos:

Entrada : test_str = ‘geeksforgeeksforgeeks’, N = 3, K = 2 
Salida : [‘gee’, ‘eek’, ‘gee’, ‘eek’, ‘gee’, ‘eek’] 
Explicación : 3 longitudes tienen 2 caracteres únicos se extraen.

Entrada : test_str = ‘geeksforgeeksforgeeks’, N = 4, K = 2 
Salida : [] 
Explicación : No hay strings con 4 longitudes y solo tiene 2 elementos. 

Método n.º 1: Usar rebanar + set() + bucle

En esto, realizamos la tarea de obtener N fragmentos mediante el corte, set() se usa para verificar elementos únicos. Loop se utiliza para iterar todos los fragmentos posibles.

# Python3 code to demonstrate working of
# N sized substrings with K distinct characters
# Using slicing + set() + loop
 
# initializing string
test_str = 'geeksforgeeksforgeeks'
 
# printing original string
print("The original string is : " + str(test_str))
 
# initializing N
N = 3
 
# initializing K
K = 2
 
res = []
for idx in range(0, len(test_str) - N + 1):
 
    # getting unique elements off sliced string
    if (len(set(test_str[idx: idx + N])) == K):
        res.append(test_str[idx: idx + N])
 
# printing result
print("Extracted Strings : " + str(res))

The original string is : geeksforgeeksforgeeks
Extracted Strings : ['gee', 'eek', 'gee', 'eek', 'gee', 'eek']

Método n.º 2: Usar comprensión de listas + len() + set() + corte

Similar al método anterior, la única diferencia es que se usa la comprensión de la lista en lugar del bucle, solo para proporcionar una abreviatura para resolver esta tarea.

# Python3 code to demonstrate working of
# N sized substrings with K distinct characters
# Using list comprehension + len() + set() + slicing
 
# initializing string
test_str = 'geeksforgeeksforgeeks'
 
# printing original string
print("The original string is : " + str(test_str))
 
# initializing N
N = 3
 
# initializing K
K = 2
 
# list comprehension used to slice
res = [test_str[idx: idx + N]
       for idx in range(0, len(test_str) - N + 1)
       if len(set(test_str[idx: idx + N])) == K]
 
# printing result
print("Extracted Strings : " + str(res))

The original string is : geeksforgeeksforgeeks
Extracted Strings : ['gee', 'eek', 'gee', 'eek', 'gee', 'eek']

La complejidad de tiempo y espacio para todos los métodos es la misma:

Complejidad de tiempo: O(n)

Complejidad espacial: O(n)