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>
Producción:
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