Dada una string S de longitud N que consiste en números de (0-9) y también dos números, uno es par (digamos X ) y uno es impar (digamos Y ) , la tarea es encontrar la substring que ocurre el tiempo máximo y solo contiene X o Y.
Nota: Si dos substrings tienen la misma frecuencia, devuelve la lexicográficamente más pequeña.
Ejemplos:
Entrada: N = 5, S =”48947″, X = ‘4’, Y = ‘9’
Salida: 4
Explicación: Substring “4” que aparece el máximo número de veces en “48947”.Entrada: N = 8, S = “22772777”, X = ‘2’, Y = ‘7’
Salida: 7
Enfoque ingenuo: el enfoque básico para resolver el problema es verificar diferentes substrings de diferentes longitudes que consisten solo en números pares e impares dados.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: el problema se puede resolver de manera eficiente con la ayuda de la siguiente observación:
Simplemente verifique la ocurrencia de dígitos pares e impares dados.
Imprima el dígito de X e Y dados, cuál ocurre el número máximo de veces.
Si ambos ocurren el mismo número de veces, la impresión lexicográficamente es mínima.
Razón: la razón por la que solo estamos comprobando la aparición del único dígito par e impar y no la aparición de la substring de longitud superior a 1:
Teniendo en cuenta la string: «22772777»
En este ejemplo, «227» y «22» ocurren 1 vez cada uno, «27» ocurre 2 veces y de manera similar para otras substrings. Pero la substring de un solo dígito «7» aparece 5 veces, que es el máximo entre todos.
El motivo es que las substrings de cualquier longitud formadas solo por X e Y dadas las contienen como substrings de longitud única. Entonces, obviamente, ocurren más veces que las otras substrings.
Es por eso que solo se necesita verificar la substring de números pares e impares de longitud 1.
Siga los pasos para resolver el problema:
- Inicializar dos variables de conteo para almacenar el conteo de X e Y.
- Atraviese la string y verifique:
- Si el carácter actual es par o impar y aumentar sus respectivas cuentas.
- Compare ambos conteos y devuelva el que tenga un conteo mayor.
- Si el recuento de ambos es el mismo, devuelva el mínimo lexicográficamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find substring
// which occur maximum number of times
char find(int N, string S, char even, char odd)
{
// Count1 for even and count2 for odd
// traversing the whole string
int count1 = 0;
int count2 = 0;
for (int i = 0; i < N; i++) {
// Checking if the character is
// equal to even
if (S[i] == even)
count1++;
// Checking if the character
// is equal to odd
else if (S[i] == odd)
count2++;
}
// If even occur maximum times
if (count1 > count2)
return even;
// If odd occur maximum times
else if (count2 > count1)
return odd;
// If both occur same times
// checking which one is
// lexicographically minimum
else {
if (even - '0' < odd - '0')
return even;
else
return odd;
}
}
// Driver Code
int main()
{
// Length of string
int N = 8;
// Even and odd number
char even = '2', odd = '7';
string S = "22772777";
// Output string
string ans;
// Calling function to find string
ans = find(N, S, even, odd);
// Printing output
cout << ans << endl;
return 0;
}
Java
// Java code for the above approach
import java.io.*;
class GFG
{
// Function to find substring
// which occur maximum number of times
public static char find(int N, String S, char even,
char odd)
{
// Count1 for even and count2 for odd
// traversing the whole string
int count1 = 0;
int count2 = 0;
for (int i = 0; i < N; i++) {
// Checking if the character is
// equal to even
if (S.charAt(i) == even)
count1++;
// Checking if the character
// is equal to odd
else if (S.charAt(i) == odd)
count2++;
}
// If even occur maximum times
if (count1 > count2)
return even;
// If odd occur maximum times
else if (count2 > count1)
return odd;
// If both occur same times
// checking which one is
// lexicographically minimum
else {
if (even - '0' < odd - '0')
return even;
else
return odd;
}
}
// Driver code
public static void main(String[] args)
{
// Length of string
int N = 8;
// Even and odd number
char even = '2', odd = '7';
String S = "22772777";
// Output string
String ans = "";
// Calling function to find string
ans += find(N, S, even, odd);
// Printing output
System.out.println(ans);
}
}
// This code is contributed by Rohit Pradhan
Python3
# python3 code for the above approach
# Function to find substring
# which occur maximum number of times
def find(N, S, even, odd):
# Count1 for even and count2 for odd
# traversing the whole string
count1 = 0
count2 = 0
for i in range(0, N):
# Checking if the character is
# equal to even
if (S[i] == even):
count1 += 1
# Checking if the character
# is equal to odd
elif (S[i] == odd):
count2 += 1
# If even occur maximum times
if (count1 > count2):
return even
# If odd occur maximum times
elif (count2 > count1):
return odd
# If both occur same times
# checking which one is
# lexicographically minimum
else:
if (ord(even) - ord('0') < ord(odd) - ord('0')):
return even
else:
return odd
# Driver Code
if __name__ == "__main__":
# Length of string
N = 8
# Even and odd number
even, odd = "2", '7'
S = "22772777"
# Output string
ans = ""
# Calling function to find string
ans = find(N, S, even, odd)
# Printing output
print(ans)
# This code is contributed by rakeshsahni
C#
// C# code for the above approach
using System;
class GFG {
// Function to find substring
// which occur maximum number of times
static char find(int N, string S, char even, char odd)
{
// Count1 for even and count2 for odd
// traversing the whole string
int count1 = 0;
int count2 = 0;
for (int i = 0; i < N; i++) {
// Checking if the character is
// equal to even
if (S[i] == even)
count1++;
// Checking if the character
// is equal to odd
else if (S[i] == odd)
count2++;
}
// If even occur maximum times
if (count1 > count2)
return even;
// If odd occur maximum times
else if (count2 > count1)
return odd;
// If both occur same times
// checking which one is
// lexicographically minimum
else {
if (even - '0' < odd - '0')
return even;
else
return odd;
}
}
// Driver code
public static int Main()
{
// Length of string
int N = 8;
// Even and odd number
char even = '2', odd = '7';
string S = "22772777";
// Output string
string ans = "";
// Calling function to find string
ans += find(N, S, even, odd);
// Printing output
Console.WriteLine(ans);
return 0;
}
}
// This code is contributed by Taranpreet
Javascript
<script>
// JavaScript code for the above approach
// Function to find substring
// which occur maximum number of times
function find(N, S, even, odd)
{
// Count1 for even and count2 for odd
// traversing the whole string
var count1 = 0;
var count2 = 0;
for (var i = 0; i < N; i++) {
// Checking if the character is
// equal to even
if (S[i] == even)
count1++;
// Checking if the character
// is equal to odd
else if (S[i] == odd)
count2++;
}
// If even occur maximum times
if (count1 > count2)
return even;
// If odd occur maximum times
else if (count2 > count1)
return odd;
// If both occur same times
// checking which one is
// lexicographically minimum
else {
if (even - '0' < odd - '0')
return even;
else
return odd;
}
}
// Driver Code
// Length of string
var N = 8;
// Even and odd number
var even = '2';
var odd = '7';
var S = "22772777";
// Output string
var ans;
// Calling function to find string
ans = find(N, S, even, odd);
// Printing output
document.write(ans);
// This code is contributed by phasing17
</script>
7
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shubhamrajput6156 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA