Dadas dos strings S y T , la tarea es encontrar el prefijo de longitud mínima de S que consta de todos los caracteres de la string T . Si S no contiene todos los caracteres de la string T , imprima -1 .
Ejemplos:
Entrada: S = “MarvoloGaunt”, T = “Tom”
Salida: 12
Explicación:
El prefijo de 12 longitudes “MarvoloGaunt” contiene todos los caracteres de “Tom”Entrada: S = “ElMundo”, T = “Dio”
Salida: -1
Explicación:
La string “ElMundo” no contiene el carácter ‘i’ de la string “Dio”.
Enfoque ingenuo:
el enfoque más simple para resolver el problema es iterar la string S y comparar la frecuencia de cada letra tanto en el prefijo como en la T y devolver la longitud recorrida si se encuentra el prefijo requerido. De lo contrario, devuelve -1.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente:
para optimizar el enfoque anterior, siga los pasos a continuación:
- Almacene las frecuencias de T en un diccionario dictCount .
- Almacene el número de letras únicas con un recuento superior a 0 como nUnique .
- Iterar sobre [0, N] y obtener el i -ésimo carácter de índice de S como ch .
- Disminuya el conteo de ch de dictCount si existe. Si este recuento llega a 0, disminuya nUnique en 1.
- Si nUnique llega a 0, devuelve la longitud recorrida hasta entonces.
- Después de completar el recorrido de S , si nUnique aún supera 0, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int getPrefixLength(string srcStr, string targetStr) { // Base Case - if T is empty, // it matches 0 length prefix if (targetStr.length() == 0) return 0; // Convert strings to lower // case for uniformity transform(srcStr.begin(), srcStr.end(), srcStr.begin(), ::tolower); transform(targetStr.begin(), targetStr.end(), targetStr.begin(), ::tolower); map<char, int> dictCount; int nUnique = 0; // Update dictCount to the // letter count of T for(char ch: targetStr) { // If new character is found, // initialize its entry, // and increase nUnique if (dictCount.find(ch) == dictCount.end()) { nUnique += 1; dictCount[ch] = 0; } // Increase count of ch dictCount[ch] += 1; } // Iterate from 0 to N for(int i = 0; i < srcStr.length(); i++) { // i-th character char ch = srcStr[i]; // Skip if ch not in targetStr if (dictCount.find(ch) == dictCount.end()) continue; // Decrease Count dictCount[ch] -= 1; // If the count of ch reaches 0, // we do not need more ch, // and can decrease nUnique if (dictCount[ch] == 0) nUnique -= 1; // If nUnique reaches 0, // we have found required prefix if (nUnique == 0) return (i + 1); } // Otherwise return -1; } // Driver code int main() { string S = "MarvoloGaunt"; string T = "Tom"; cout << getPrefixLength(S, T); return 0; } // This code is contributed by divyeshrabadiya07
Java
// Java program for the above approach import java.util.*; public class Main { public static int getPrefixLength(String srcStr, String targetStr) { // Base Case - if T is empty, // it matches 0 length prefix if (targetStr.length() == 0) return 0; // Convert strings to lower // case for uniformity srcStr = srcStr.toLowerCase(); targetStr = targetStr.toLowerCase(); HashMap<Character, Integer> dictCount = new HashMap<>(); int nUnique = 0; // Update dictCount to the // letter count of T for(char ch : targetStr.toCharArray()) { // If new character is found, // initialize its entry, // and increase nUnique if (dictCount.containsKey(ch) != true) { nUnique += 1; dictCount.put(ch, 0); } // Increase count of ch dictCount.replace(ch, dictCount.get(ch) + 1); } // Iterate from 0 to N for(int i = 0; i < srcStr.length(); i++) { // i-th character char ch = srcStr.charAt(i); // Skip if ch not in targetStr if (dictCount.containsKey(ch) != true) continue; // Decrease Count dictCount.replace(ch, dictCount.get(ch) - 1); // If the count of ch reaches 0, // we do not need more ch, // and can decrease nUnique if (dictCount.get(ch) == 0) nUnique -= 1; // If nUnique reaches 0, // we have found required prefix if (nUnique == 0) return (i + 1); } // Otherwise return -1; } // Driver code public static void main(String[] args) { String S = "MarvoloGaunt"; String T = "Tom"; System.out.println(getPrefixLength(S, T)); } } // This code is contributed by divyesh072019
Python3
# Python3 program for the above approach def getPrefixLength(srcStr, targetStr): # Base Case - if T is empty, # it matches 0 length prefix if(len(targetStr) == 0): return 0 # Convert strings to lower # case for uniformity srcStr = srcStr.lower() targetStr = targetStr.lower() dictCount = dict([]) nUnique = 0 # Update dictCount to the # letter count of T for ch in targetStr: # If new character is found, # initialize its entry, # and increase nUnique if(ch not in dictCount): nUnique += 1 dictCount[ch] = 0 # Increase count of ch dictCount[ch] += 1 # Iterate from 0 to N for i in range(len(srcStr)): # i-th character ch = srcStr[i] # Skip if ch not in targetStr if(ch not in dictCount): continue # Decrease Count dictCount[ch] -= 1 # If the count of ch reaches 0, # we do not need more ch, # and can decrease nUnique if(dictCount[ch] == 0): nUnique -= 1 # If nUnique reaches 0, # we have found required prefix if(nUnique == 0): return (i + 1) # Otherwise return -1 # Driver Code if __name__ == "__main__": S = "MarvoloGaunt" T = "Tom" print(getPrefixLength(S, T))
C#
// C# program for the above approach using System.Collections.Generic; using System; class GFG{ static int getPrefixLength(string srcStr, string targetStr) { // Base Case - if T is empty, // it matches 0 length prefix if (targetStr.Length == 0) return 0; // Convert strings to lower // case for uniformity srcStr = srcStr.ToLower(); targetStr = targetStr.ToLower(); Dictionary<char, int> dictCount = new Dictionary<char, int>(); int nUnique = 0; // Update dictCount to the // letter count of T foreach(var ch in targetStr) { // If new character is found, // initialize its entry, // and increase nUnique if (dictCount.ContainsKey(ch) != true) { nUnique += 1; dictCount[ch] = 0; } // Increase count of ch dictCount[ch] += 1; } // Iterate from 0 to N for(int i = 0; i < srcStr.Length; i++) { // i-th character char ch = srcStr[i]; // Skip if ch not in targetStr if (dictCount.ContainsKey(ch) != true) continue; // Decrease Count dictCount[ch] -= 1; // If the count of ch reaches 0, // we do not need more ch, // and can decrease nUnique if (dictCount[ch] == 0) nUnique -= 1; // If nUnique reaches 0, // we have found required prefix if (nUnique == 0) return (i + 1); } // Otherwise return -1; } // Driver code public static void Main() { string S = "MarvoloGaunt"; string T = "Tom"; Console.Write(getPrefixLength(S, T)); } } // This code is contributed by Stream_Cipher
Javascript
<script> // JavaScript program for the above approach function getPrefixLength(srcStr, targetStr) { // Base Case - if T is empty, // it matches 0 length prefix if (targetStr.length === 0) return 0; // Convert strings to lower // case for uniformity srcStr = srcStr.toLowerCase(); targetStr = targetStr.toLowerCase(); var dictCount = {}; var nUnique = 0; // Update dictCount to the // letter count of T for (const ch of targetStr) { // If new character is found, // initialize its entry, // and increase nUnique if (dictCount.hasOwnProperty(ch) !== true) { nUnique += 1; dictCount[ch] = 0; } // Increase count of ch dictCount[ch] += 1; } // Iterate from 0 to N for (var i = 0; i < srcStr.length; i++) { // i-th character var ch = srcStr[i]; // Skip if ch not in targetStr if (dictCount.hasOwnProperty(ch) !== true) continue; // Decrease Count dictCount[ch] -= 1; // If the count of ch reaches 0, // we do not need more ch, // and can decrease nUnique if (dictCount[ch] === 0) nUnique -= 1; // If nUnique reaches 0, // we have found required prefix if (nUnique === 0) return i + 1; } // Otherwise return -1; } // Driver code var S = "MarvoloGaunt"; var T = "Tom"; document.write(getPrefixLength(S, T)); </script>
12
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por joshi_arihant y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA