Operaciones mínimas tales que cada segmento dado de String tenga caracteres distintos

 Dada una string S de longitud N , Q rangos de la forma [L, R] en un rango de array 2D y una permutación arr [] que contiene números del 1 al N . En una operación, puede eliminar el primer carácter no eliminado según la permutación. Sin embargo, las posiciones de otros personajes no cambiarán. Determine el número mínimo de operaciones que siguen las siguientes condiciones:

• Todos los caracteres en cada uno de los rangos Q son distintos. Los caracteres eliminados no se cuentan.
• Se considera que un rango con todos los caracteres eliminados tiene todos los caracteres distintos.
• La secuencia de n enteros se llama permutación si contiene todos los enteros del 1 al n exactamente una vez.

Nota: Se sigue la indexación basada en 1.

Ejemplos:

Entrada: N = 5, Q = 2, S = “aaaa”, arr[] = {2, 4, 1, 3, 5}, rangos = {{1, 2}, {4, 5}}
Salida: 2
Explicación: Después de la primera operación, la string se convierte en a_aaa
Después de la segunda operación, la string se convierte en a_a_a
Ahora, en ambos rangos, todos los caracteres son distintos.
Por lo tanto, la salida es 2.

Entrada: N = 8, Q = 3, S = “abbabaab”, arr[] = {6, 3, 5, 1, 4, 2, 7, 8}, rangos = {{1, 3}, {4, 7}, {3, 5}}
Salida: 5
Explicación: Después de la primera operación, la string se convierte en abbab_ab
Después de la segunda operación, la string se convierte en ab_ab_ab
Después de la tercera operación, la string se convierte en ab_a_ _ab
Después de la cuarta operación, la string se convierte en _b_a_ _ab
Después de la quinta operación, la string se convierte en _b_ _ _ _ab
Ahora, en todos los rangos, todos los caracteres son distintos.
Por lo tanto, la salida es 5.

Enfoque: Para resolver el problema, siga la siguiente idea: 

Una forma fácil es atravesar la permutación y eliminar caracteres en serie. En cada recorrido, recorreremos cada consulta para encontrar si todos contienen caracteres únicos. Si la respuesta llega a ser positiva, devolver el número de recorridos es la respuesta final.

Siga los pasos a continuación para resolver el problema:

• Si todas las consultas tienen caracteres únicos, devuelva 0 .
• Atraviese la permutación arr[] de i = 0 a N-1 :
  • Inicialice (arr[i] – 1) el índice con ‘_’ en una lista temporal y llame a isValid .
  • Dentro de la función isValid :
    • Recorra los rangos de consulta usando el iterador j .
      • Si temp[j] != ‘_’ entonces presione temp[j] en una array (digamos ss ).
      • Si la longitud del conjunto formado por ss no es igual a la longitud de ss , entonces hay caracteres que se repiten, por lo que devuelve False .
      • De lo contrario, devuelve True .
  • Si isValid devuelve True , devuelve i+1 como respuesta final.
  • De lo contrario, devuelve -1 .

A continuación se muestra la implementación del enfoque anterior.

# Python program for the above approach:
def IsValid(temp, ranges):
    for i in range(len(ranges)):
        x, y = ranges[i]
        ss = []
        for j in range(x - 1, y):
            if temp[j] != '_':
                ss.append(temp[j])
        if len(set(ss)) != len(ss):
            return False
    return True
  
def goodString (N, Q, S, arr, ranges):
    temp = list(S)
    if IsValid(temp, ranges):
        return 0
    for i in range(len(arr)):
        temp[arr[i] - 1] = '_'
        if IsValid(temp, ranges):
            return i + 1 
    return -1
  
# driver's code
N = 8
Q = 3
S = "abbabaab"
arr = [6, 3, 5, 1, 4, 2, 7, 8]
ranges = [[1, 3], [4, 7], [3, 5]]
  
print (goodString(N, Q, S, arr, ranges))

5

Complejidad de tiempo: O(N * Q * M) donde M es el rango máximo
Espacio auxiliar: O(N)