data-structure.algo

/*
Approach: 

Check if the string has at least K unique characters if no then prints 
the error message and stop.
Let’s say we take substring between indexes curr_start and curr_end, 
both points to index 0 at the beginning.
Keep adding one character at a time to the substring by moving curr_end
pointer to the right and make sure that condition of substring has at 
most K unique characters , is valid by adding the new character and if 
any point the condition is not valid then start moving curr_start pointer 
to the right till condition is valid again.
At each step, keep track of the length of a maximum substring by doing curr_end-curr_start.  
To check whether substring has only K unique characters, maintain an array of size 26 
( 26 alphabets) and the array is filled with the count of characters in the string to 
the respective index. 0th index for ‘a’ and 25th index for z.
See the example below for more understanding.








Vérifiez si la chaîne a au moins K caractères uniques si non alors imprime
le message d'erreur et s'arrêter.
Disons que nous prenons une sous-chaîne entre les index curr_start et curr_end,
les deux points à l'index 0 au début.
Continuez à ajouter un caractère à la fois à la sous-chaîne en déplaçant curr_end
pointeur vers la droite et assurez-vous que la condition de la sous-chaîne a à
la plupart des K caractères uniques , est valide en ajoutant le nouveau caractère et si
n'importe quel point la condition n'est pas valide alors commencez à déplacer le pointeur curr_start
à droite jusqu'à ce que la condition soit à nouveau valide.
À chaque étape, gardez une trace de la longueur d'une sous-chaîne maximale en faisant curr_end-curr_start.
Pour vérifier si la sous-chaîne n'a que K caractères uniques, maintenez un tableau de taille 26
(26 alphabets) et le tableau est rempli avec le nombre de caractères dans la chaîne à
l'indice respectif. 0e indice pour « a » et 25e indice pour z.
Voir l'exemple ci-dessous pour plus de compréhension.


*/


ALGORITHM K_unique_characters
VAR
    str : STRING[50];
    k, i, j, count : INTEGER;
    diff : BOOLEAN;
    max_start, max_length, curr_start, curr_end : INTEGER := 0;
    alpha_count : HASH_TABLE<CHAR,INTEGER>;
    
BEGIN
    Read(str);
    Read(k);
    count :=0;
    FOR i FROM 0 TO str.length-1 DO
        diff := TRUE;
        FOR j FROM i+1 TO str.length-1 DO
            IF (str[i] = str[j]) THEN
                diff := FALSE;
                BREAK;
            END_IF
        END_FOR
        IF (diff) THEN
            count := count +1;
        END_IF
    END_FOR

    IF (count < k) THEN
        Write("Not enough unique character is present in the input string");
    ELSE

    FOR i FROM 0 TO str.length-1  DO
        IF (alpha_count.lookup(str[i]) = TRUE) THEN
            count := alpha_count.get(str[i]);
            alpha_count.insert(str[i],count+1);
        ELSE
            alpha_count.insert(str[i],1);
        END_IF
        curr_end := curr_end +1;
        //vérifier si un nouveau caractère est ajouté ou
        // si le nombre de caractères uniques est au plus k
        //in the window
        WHILE (alpha_count.getKeys().length > k) DO
            count := alpha_count.get(str[curr_start]);
            alpha_count.insert(str[curr_start],count-1);
            curr_start := curr_start +1;
        END_WHILE

        //vérifier si max_length doit être mis à jour
        IF (curr_end - curr_start > max_length) THEN
            max_start := curr_start ;
            max_length := curr_end - curr_start ;
        END_IF
        
    END_FOR
    Write("Longest substring most unique characters is : ")
    FOR i FROM max_start TO max_start+max_length-1 DO
        Write(str[i]);
    END_FOR
    END_IF

END


Étant donné une chaîne, écrivez un algorithme pour trouver la sous-chaîne la plus longue avec au plus K caractères.
Exemple:
Entrée : aabbaacdeeeeddded, K = 3
Sortie : la sous-chaîne la plus longue avec les 3 caractères les plus uniques est : cdeeeeddded avec une longueur de 11
Entrée : abcddefabc, K = 4
Sortie : la sous-chaîne la plus longue avec les 4 caractères les plus uniques est : abcdd avec une longueur de 5
Entrée : aaaabbbb, K = 4
Sortie : Il n'y a pas assez de caractère unique dans la chaîne d'entrée