Étant donné une chaîne S composé de N alphabets anglais minuscules, et aussi étant donné qu’un caractère C est appelé K-incroyable, si chaque sous-chaîne de longueur au moins K contient ce caractère C, la tâche est de trouver le minimum possible K tel qu’il existe au moins un K-incroyable personnage.
Exemples:
Saisir: S = « abcde »
Sortir: 3
Explication:
Chaque sous-chaîne d’au moins 3, a un caractère K-amazing, ‘c’ : {« abc », « bcd », « cde », « abcd », « bcde », « abcde »}.
Saisir: S = « aaaa »
Sortir: 1
Explication:
Chaque sous-chaîne de longueur au moins 1, a un caractère K-étonnant, ‘a’ : {« a », « aa », « aaa », « aaaa »}.
Pour l’approche de recherche naïve et binaire, reportez-vous Ensemble 1
Approcher: L’approche naïve peut être optimisée en partant du constat que pour un personnage ‘C‘ existe dans chaque sous-chaîne de longueur K, la distance entre les positions de deux ‘ consécutifsC‘ ne peut pas dépasser K. Suivez les étapes ci-dessous pour résoudre le problème :
- Initialiser une variable entière, disons ans comme N, qui stockera la taille minimale de la sous-chaîne possible de telle sorte que chaque sous-chaîne de taille ans a au moins un K-incroyable personnage.
- Insérez le caractère ‘0‘ au début et à la fin de la chaîne S.
- Itérer sur les caractères de la plage [a, z] en utilisant la variable c et effectuez les étapes suivantes :
- Attribuer un personnage c à S[0] et S[N+1].
- Initialisez deux variables, disons précédent comme 0 et maxLen comme 0, où précédent stockera le dernier index du caractère c et maxLen mémorisera la distance maximale entre les positions des deux plus proches c.
- Itérer sur la plage [1, N+1] en utilisant la variable je et effectuez les étapes suivantes :
- Si S[i] = c, puis modifiez la valeur de maxLen à max(maxLen, i – précédent) et puis attribuer je à précédent.
- Modifiez maintenant la valeur de ans à min(ans, max_len).
- Enfin, après avoir terminé les étapes ci-dessus, imprimez la valeur de ans obtenu.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++
|
#include en utilisant l’espace de noms std ; int MinimumLengthSubstring(chaîne S, int N) { int ans = N; S = « 0 » + S + « 0 » ; pour (car c = ‘a’; c <= 'z'; ++c) { int précédent = 0 ; int max_len = 0; S[0] = c; S[N + 1] = c; pour (int i = 1; i <= N + 1; ++i) { si (S[i] == c) { int len = i – préc; max_len = max(max_len, len); précédent = je; } } ans = min(ans, max_len); } retour ans; } int main() { chaîne S = « abcde » ; int N = S.longueur(); cout << MinimumLengthSubstring(S, N); } |
Python3
|
def MinimumLengthSubstring(S, N): ans = N S = « 0 » + S + « 0 » S = [i for i in S] pour c dans range(ord(‘a’), ord(‘z’) + 1) : précédent = 0 max_len = 0 S[0] = chr(c) S[N + 1] = chr(c) pour i dans la plage (1, N + 2) : si (S[i] == chr(c)): len = i – précédent max_len = max(max_len, len) précédent = je ans = min(ans, max_len) retour et if __name__ == ‘__main__’ : S = « abcde » N = lentille(S) print(MinimumLengthSubstring(S, N)) |
C#
|
en utilisant le système ; en utilisant System.Collections.Generic ; classe GFG{ static int MinimumLengthSubstring(string S, int N) { int ans = N; S = « 0 » + S + « 0 » ; pour (car c = ‘a’; c <= 'z'; ++c) { int précédent = 0 ; int max_len = 0; S = S.Sous-chaîne(0,0) + c + S.Sous-chaîne(1) ; S = S.Sous-chaîne(0, N+1) + c + S.Sous-chaîne(N + 2); pour (int i = 1; i <= N + 1; ++i) { si (S[i] == c) { int len = i – préc; max_len = Math.Max(max_len, len); précédent = je; } } ans = Math.Min(ans, max_len); } retour ans; } public statique vide Main() { chaîne S = « abcde » ; int N = S.Longueur; Console.Write(MinimumLengthSubstring(S, N)); } } |
Javascript
Complexité temporelle : AU)
Espace auxiliaire : O(1)
Attention lecteur ! N’arrêtez pas d’apprendre maintenant. Obtenez tous les concepts importants de DSA avec le Cours auto-rythmé DSA à un prix adapté aux étudiants et devenez prêt pour l’industrie. Pour compléter votre préparation de l’apprentissage d’une langue à DS Algo et bien d’autres, veuillez vous référer Cours complet de préparation aux entretiens.
Au cas où vous souhaiteriez assister cours en direct avec des experts, veuillez vous référer Cours en direct DSA pour les professionnels en activité et Programmation compétitive en direct pour les étudiants.
