Dada una string str y otra string patt . Encuentre el carácter en patt que está presente en el índice mínimo en str . Si ningún carácter de patt está presente en str , imprima ‘No hay carácter presente’.
Ejemplos :
Entrada : str = “geeksforgeeks”, patt = “set”
Salida : e
Tanto e como s de patt están presentes en str ,
pero e está presente en el índice mínimo, que es 1 .Entrada : str = “adcffaet”, patt = “onkl”
Salida : Ningún carácter presente
Fuente: OLA Entrevista Experiencia | conjunto 12 .
Enfoque ingenuo: utilizando dos bucles, busque el primer índice de cada carácter de patt en str . Imprime el carácter que tiene el índice mínimo. Si no hay ningún carácter de patt presente en str , imprima «No hay carácter presente».
Implementación:
C++
// C++ implementation to find the character in
// first string that is present at minimum index
// in second string
#include <bits/stdc++.h>
using namespace std;
// function to find the minimum index character
void printMinIndexChar(string str, string patt)
{
// to store the index of character having
// minimum index
int minIndex = INT_MAX;
// lengths of the two strings
int m = str.size();
int n = patt.size();
// traverse 'patt'
for (int i = 0; i < n; i++) {
// for each character of 'patt' traverse 'str'
for (int j = 0; j < m; j++) {
// if patt[i] is found in 'str', check if
// it has the minimum index or not. If yes,
// then update 'minIndex' and break
if (patt[i] == str[j] && j < minIndex) {
minIndex = j;
break;
}
}
}
// print the minimum index character
if (minIndex != INT_MAX)
cout << "Minimum Index Character = "
<< str[minIndex];
// if no character of 'patt' is present in 'str'
else
cout << "No character present";
}
// Driver program to test above
int main()
{
string str = "geeksforgeeks";
string patt = "set";
printMinIndexChar(str, patt);
return 0;
}
Java
// Java implementation to find the character in
// first string that is present at minimum index
// in second string
public class GFG
{
// method to find the minimum index character
static void printMinIndexChar(String str, String patt)
{
// to store the index of character having
// minimum index
int minIndex = Integer.MAX_VALUE;
// lengths of the two strings
int m = str.length();
int n = patt.length();
// traverse 'patt'
for (int i = 0; i < n; i++) {
// for each character of 'patt' traverse 'str'
for (int j = 0; j < m; j++) {
// if patt.charAt(i)is found in 'str', check if
// it has the minimum index or not. If yes,
// then update 'minIndex' and break
if (patt.charAt(i)== str.charAt(j) && j < minIndex) {
minIndex = j;
break;
}
}
}
// print the minimum index character
if (minIndex != Integer.MAX_VALUE)
System.out.println("Minimum Index Character = " +
str.charAt(minIndex));
// if no character of 'patt' is present in 'str'
else
System.out.println("No character present");
}
// Driver Method
public static void main(String[] args)
{
String str = "geeksforgeeks";
String patt = "set";
printMinIndexChar(str, patt);
}
}
Python3
# Python3 implementation to find the character in
# first that is present at minimum index
# in second String
# function to find the minimum index character
def printMinIndexChar(Str, patt):
# to store the index of character having
# minimum index
minIndex = 10**9
# lengths of the two Strings
m =len(Str)
n =len(patt)
# traverse 'patt'
for i in range(n):
# for each character of 'patt' traverse 'Str'
for j in range(m):
# if patt[i] is found in 'Str', check if
# it has the minimum index or not. If yes,
# then update 'minIndex' and break
if (patt[i] == Str[j] and j < minIndex):
minIndex = j
break
# print the minimum index character
if (minIndex != 10**9):
print("Minimum Index Character = ",Str[minIndex])
# if no character of 'patt' is present in 'Str'
else:
print("No character present")
# Driver code
Str = "geeksforgeeks"
patt = "set"
printMinIndexChar(Str, patt)
# This code is contributed by mohit kumar 29
C#
// C# implementation to find the character in
// first string that is present at minimum index
// in second string
using System;
class GFG
{
// method to find the minimum index character
static void printMinIndexChar(String str, String patt)
{
// to store the index of character having
// minimum index
int minIndex = int.MaxValue;
// lengths of the two strings
int m = str.Length;
int n = patt.Length;
// traverse 'patt'
for (int i = 0; i < n; i++) {
// for each character of 'patt' traverse 'str'
for (int j = 0; j < m; j++) {
// if patt.charAt(i)is found in 'str', check if
// it has the minimum index or not. If yes,
// then update 'minIndex' and break
if (patt[i]== str[j] && j < minIndex) {
minIndex = j;
break;
}
}
}
// print the minimum index character
if (minIndex != int.MaxValue)
Console.WriteLine("Minimum Index Character = " +
str[minIndex]);
// if no character of 'patt' is present in 'str'
else
Console.WriteLine("No character present");
}
// Driver Methoda
public static void Main()
{
String str = "geeksforgeeks";
String patt = "set";
printMinIndexChar(str, patt);
}
}
// This code is contributed by Sam007
Javascript
<script>
// Javascript implementation to find the character in
// first string that is present at minimum index
// in second string
// method to find the minimum index character
function printMinIndexChar(str,patt)
{
// to store the index of character having
// minimum index
let minIndex = Number.MAX_VALUE;
// lengths of the two strings
let m = str.length;
let n = patt.length;
// traverse 'patt'
for (let i = 0; i < n; i++) {
// for each character of 'patt' traverse 'str'
for (let j = 0; j < m; j++) {
// if patt.charAt(i)is found in 'str', check if
// it has the minimum index or not. If yes,
// then update 'minIndex' and break
if (patt[i]== str[j] && j < minIndex) {
minIndex = j;
break;
}
}
}
// print the minimum index character
if (minIndex != Number.MAX_VALUE)
document.write("Minimum Index Character = " +
str[minIndex]);
// if no character of 'patt' is present in 'str'
else
document.write("No character present");
}
// Driver Method
let str = "geeksforgeeks";
let patt = "set";
printMinIndexChar(str, patt);
//This code is contributed by rag2127
</script>
Producción
Minimum Index Character = e
Complejidad de tiempo: O(mn) , donde m y n son las longitudes de las dos strings.
Espacio Auxiliar: O(1)
Método 2 Enfoque Eficiente (Hashing):
- Cree una tabla hash con tupla (clave, valor) representada como tupla (carácter, índice) .
- Almacene el primer índice de cada carácter de str en la tabla hash.
- Ahora, para cada carácter de patt , compruebe si está presente en la tabla hash o no.
- Si está presente, obtenga su índice de la tabla hash y actualice minIndex (índice mínimo encontrado hasta ahora).
- Si no hay ningún carácter coincidente, escriba «No hay carácter presente».
La tabla hash se implementa usando unordered_set en C++ .
La siguiente imagen es una ejecución en seco del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the character in first
// string that is present at minimum index in second
// string
#include <bits/stdc++.h>
using namespace std;
// function to find the minimum index character
void printMinIndexChar(string str, string patt)
{
// unordered_map 'um' implemented as hash table
unordered_map<char, int> um;
// to store the index of character having
// minimum index
int minIndex = INT_MAX;
// lengths of the two strings
int m = str.size();
int n = patt.size();
// store the first index of each character of 'str'
for (int i = 0; i < m; i++) {
if (um.find(str[i]) == um.end())
um[str[i]] = i;
}
// traverse the string 'patt'
for (int j = 0; j < n; j++) {
// if patt[i] is found in 'um', check if
// it has the minimum index or not accordingly
// update 'minIndex'
if (um.find(patt[j]) != um.end()
&& um[patt[j]] < minIndex)
minIndex = um[patt[j]];
}
// print the minimum index character
if (minIndex != INT_MAX)
cout << "Minimum Index Character = "
<< str[minIndex];
// if no character of 'patt' is present in 'str'
else
cout << "No character present";
}
// Driver program to test above
int main()
{
string str = "geeksforgeeks";
string patt = "set";
printMinIndexChar(str, patt);
return 0;
}
Java
// Java implementation to find the character in
// first string that is present at minimum index
// in second string
import java.util.HashMap;
public class GFG
{
// method to find the minimum index character
static void printMinIndexChar(String str, String patt)
{
// map to store the first index of each character of 'str'
HashMap<Character, Integer> hm = new HashMap<>();
// to store the index of character having
// minimum index
int minIndex = Integer.MAX_VALUE;
// lengths of the two strings
int m = str.length();
int n = patt.length();
// store the first index of each character of 'str'
for (int i = 0; i < m; i++)
if(!hm.containsKey(str.charAt(i)))
hm.put(str.charAt(i),i);
// traverse the string 'patt'
for (int i = 0; i < n; i++)
// if patt[i] is found in 'um', check if
// it has the minimum index or not accordingly
// update 'minIndex'
if (hm.containsKey(patt.charAt(i)) &&
hm.get(patt.charAt(i)) < minIndex)
minIndex = hm.get(patt.charAt(i));
// print the minimum index character
if (minIndex != Integer.MAX_VALUE)
System.out.println("Minimum Index Character = " +
str.charAt(minIndex));
// if no character of 'patt' is present in 'str'
else
System.out.println("No character present");
}
// Driver Method
public static void main(String[] args)
{
String str = "geeksforgeeks";
String patt = "set";
printMinIndexChar(str, patt);
}
}
Python3
# Python3 implementation to
# find the character in first
# string that is present at
# minimum index in second string
import sys
# Function to find the
# minimum index character
def printMinIndexChar(st, patt):
# unordered_map 'um'
# implemented as hash table
um = {}
# to store the index of
# character having minimum index
minIndex = sys.maxsize
# Lengths of the two strings
m = len(st)
n = len(patt)
# Store the first index of
# each character of 'str'
for i in range (m):
if (st[i] not in um):
um[st[i]] = i
# traverse the string 'patt'
for i in range(n):
# If patt[i] is found in 'um',
# check if it has the minimum
# index or not accordingly
# update 'minIndex'
if (patt[i] in um and
um[patt[i]] < minIndex):
minIndex = um[patt[i]]
# Print the minimum index character
if (minIndex != sys.maxsize):
print ("Minimum Index Character = ",
st[minIndex])
# If no character of 'patt'
# is present in 'str'
else:
print ("No character present")
# Driver program to test above
if __name__ == "__main__":
st = "geeksforgeeks"
patt = "set"
printMinIndexChar(st, patt)
# This code is contributed by Chitranayal
C#
// C# implementation to find the character in
// first string that is present at minimum index
// in second string
using System;
using System.Collections.Generic;
class GFG
{
// method to find the minimum index character
static void printMinIndexChar(String str, String patt)
{
// map to store the first index of
// each character of 'str'
Dictionary<char,
int> hm = new Dictionary<char,
int>();
// to store the index of character having
// minimum index
int minIndex = int.MaxValue;
// lengths of the two strings
int m = str.Length;
int n = patt.Length;
// store the first index of
// each character of 'str'
for (int i = 0; i < m; i++)
if(!hm.ContainsKey(str[i]))
hm.Add(str[i], i);
// traverse the string 'patt'
for (int i = 0; i < n; i++)
// if patt[i] is found in 'um',
// check if it has the minimum index
// or not, accordingly update 'minIndex'
if (hm.ContainsKey(patt[i]) &&
hm[patt[i]] < minIndex)
minIndex = hm[patt[i]];
// print the minimum index character
if (minIndex != int.MaxValue)
Console.WriteLine("Minimum Index Character = " +
str[minIndex]);
// if no character of 'patt' is present in 'str'
else
Console.WriteLine("No character present");
}
// Driver Code
public static void Main(String[] args)
{
String str = "geeksforgeeks";
String patt = "set";
printMinIndexChar(str, patt);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation to find the
// character in first string that is
// present at minimum index in second
// string
// Method to find the minimum index character
function printMinIndexChar(str, patt)
{
// map to store the first index of
// each character of 'str'
let hm = new Map();
// To store the index of character having
// minimum index
let minIndex = Number.MAX_VALUE;
// Lengths of the two strings
let m = str.length;
let n = patt.length;
// Store the first index of
// each character of 'str'
for(let i = 0; i < m; i++)
if (!hm.has(str[i]))
hm.set(str[i], i);
// Traverse the string 'patt'
for(let i = 0; i < n; i++)
// If patt[i] is found in 'um', check
// if it has the minimum index or not
// accordingly update 'minIndex'
if (hm.has(patt[i]) &&
hm.get(patt[i]) < minIndex)
minIndex = hm.get(patt[i]);
// Print the minimum index character
if (minIndex != Number.MAX_VALUE)
document.write("Minimum Index Character = " +
str[minIndex]);
// If no character of 'patt' is
// present in 'str'
else
document.write("No character present");
}
// Driver Code
let str = "geeksforgeeks";
let patt = "set";
printMinIndexChar(str, patt);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Minimum Index Character = e
Complejidad de tiempo: O(m + n), donde m y n son las longitudes de las dos strings.
Espacio auxiliar: O(d) , donde d es el tamaño de la tabla hash, que es el recuento de caracteres distintos en str .
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA