Compruebe si una string contiene algún índice con más de K caracteres activos

Dada una string S , que contiene alfabetos ingleses en minúsculas, y un número entero K , la tarea es encontrar cualquier índice de la string que consta de más de K caracteres activos. Si lo encuentra, imprima Sí . De lo contrario , imprima No.

El recuento de caracteres activos para cualquier índice es el número de caracteres que tienen apariciones anteriores antes o en el índice actual y la última aparición en o después del índice actual.

Ejemplos:

Entrada: S = “aabbcd”, K = 1 
Salida: No 
Explicación: 
Índice 1: Carácter activo: a 
Índice 2: Carácter activo: a 
Índice 3: Carácter activo: b 
Índice 4: Carácter activo: b 
Índice 5: Carácter activo: c 
Índice 6: Carácter activo: d 
No hay más de un carácter activo en cualquier índice de la string.
Entrada: S = “aabbcdca”, K = 2 
Salida: Sí 
Explicación: 
Índice 1: Carácter activo: a 
Índice 2: Carácter activo: a 
Índice 3: Caracteres activos: a, b 
Índice 4: Caracteres activos: a, b 
Índice 5 : Caracteres activos : a, c 
Índice 6: Caracteres activos : a, c, d 
Por lo tanto, existe un índice con más de 2 caracteres activos.

Enfoque: 
siga los pasos a continuación para resolver el problema:

• La idea es almacenar la última aparición de cada carácter presente en la string en un Map .
• Atraviese la string y siga almacenando letras activas en un Set .
• Si en algún índice, el tamaño del Conjunto excede K , escriba “Sí” .
• De lo contrario, compruebe si el índice actual es la última aparición del carácter actual. Si es así, elimine el personaje del Conjunto .
• Finalmente, si no encuentra ningún índice con más de K caracteres activos, imprima “No” .

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if any index
// contains more than K active characters
string checkString(string s, int K)
{
 
    int n = s.length();
 
    // Store the last occurrence of
    // each character in the map.
    unordered_map<char, int> mp;
 
    for (int i = 0; i < n; i++) {
        mp[s[i]] = i;
    }
 
    int cnt = 0, f = 0;
 
    // Stores the active
    // characters
    unordered_set<int> st;
 
    for (int i = 0; i < n; i++) {
 
        // Insert the character
        st.insert(s[i]);
 
        // If the size of set
        // exceeds K
        if (st.size() > K) {
            f = 1;
            break;
        }
 
        // Remove the character from
        // set if i is the last index
        // of the current character
        if (mp[s[i]] == i)
            st.erase(s[i]);
    }
 
    return (f == 1 ? "Yes" : "No");
}
 
// Driver Code
int main()
{
 
    string s = "aabbcdca";
    int k = 2;
    cout << checkString(s, k);
    return 0;
}

// Java program to implement the
// above approach
import java.util.*;
 
class GFG{
 
// Function to check if any index
// contains more than K active characters
static String checkString(String s, int K)
{
    int n = s.length();
 
    // Store the last occurrence of
    // each character in the map.
    Map<Character,
        Integer> mp = new HashMap<>();
 
    for(int i = 0; i < n; i++)
    {
        mp.put(s.charAt(i), i);
    }
 
    int cnt = 0, f = 0;
 
    // Stores the active
    // characters
    Set<Character> st = new HashSet<>();
 
    for(int i = 0; i < n; i++)
    {
         
        // Insert the character
        st.add(s.charAt(i));
 
        // If the size of set
        // exceeds K
        if (st.size() > K)
        {
            f = 1;
            break;
        }
 
        // Remove the character from
        // set if i is the last index
        // of the current character
        if (mp.get(s.charAt(i)) == i)
            st.remove(s.charAt(i));
    }
    return (f == 1 ? "Yes" : "No");
}
 
// Driver code
public static void main(String[] args)
{
    String s = "aabbcdca";
    int k = 2;
     
    System.out.println(checkString(s, k));
}
}
 
// This code is contributed by offbeat

# Python3 program to implement
# the above approach
 
# Function to check if any index
# contains more than K active characters
def checkString(s, K):
     
    n = len(s)
     
    # Store the last occurrence of
    # each character 
    dict = {}
 
    for i in range(n):
        dict[s[i]] = i;
         
    # Stores the active
    # characters
    st = set()
 
    for i in range(n):
         
        # Insert the character
        st.add(s[i])
         
        # If the size of set
        # exceeds K
        if len(st) > K:
            print("Yes")
            return
         
        # Remove the character from
        # set if i is the last index
        # of the current character
        if dict[s[i]] == i:
            st.remove(s[i])
 
    print("No")
 
# Driver code
s = "aabbcdca"
K = 2
 
checkString(s, K)
 
# This code is contributed by vashisthamadhur2

// C# program to implement the
// above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to check if any index
// contains more than K active characters
static String checkString(String s, int K)
{
    int n = s.Length;
 
    // Store the last occurrence of
    // each character in the map.
    Dictionary<char,
               int> mp = new Dictionary<char,
                                        int>();
 
    for(int i = 0; i < n; i++)
    {
        if(mp.ContainsKey(s[i]))
            mp[s[i]] = i;
        else
            mp.Add(s[i], i);
    }
 
    int f = 0;
 
    // Stores the active
    // characters
    HashSet<char> st = new HashSet<char>();
 
    for(int i = 0; i < n; i++)
    {
         
        // Insert the character
        st.Add(s[i]);
 
        // If the size of set
        // exceeds K
        if (st.Count > K)
        {
            f = 1;
            break;
        }
 
        // Remove the character from
        // set if i is the last index
        // of the current character
        if (mp[s[i]] == i)
            st.Remove(s[i]);
    }
    return (f == 1 ? "Yes" : "No");
}
 
// Driver code
public static void Main(String[] args)
{
    String s = "aabbcdca";
    int k = 2;
     
    Console.WriteLine(checkString(s, k));
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript Program to implement
// the above approach
 
// Function to check if any index
// contains more than K active characters
function checkString(s, K)
{
 
    var n = s.length;
 
    // Store the last occurrence of
    // each character in the map.
    var mp = new Map();
 
    for (var i = 0; i < n; i++) {
        if(mp.has(s[i]))
        {
            mp.set(s[i], mp.get(s[i])+1);
        }
        else
            mp.set(s[i], 1);
    }
 
    var cnt = 0, f = 0;
 
    // Stores the active
    // characters
    var st = new Set();
 
    for (var i = 0; i < n; i++) {
 
        // Insert the character
        st.add(s[i]);
 
        // If the size of set
        // exceeds K
        if (st.size > K) {
            f = 1;
            break;
        }
 
        // Remove the character from
        // set if i is the last index
        // of the current character
        if (mp.get(s[i]) == i)
            st.delete(s[i]);
    }
 
    return (f == 1 ? "Yes" : "No");
}
 
// Driver Code
var s = "aabbcdca";
var k = 2;
document.write( checkString(s, k));
 
// This code is contributed by importantly.
</script>

Yes

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)