Dada una string str[] de N alfabetos ingleses en minúsculas, la tarea es verificar si existe una substring de la string dada tal que la substring esté compuesta de solo dos caracteres y la frecuencia del 1er carácter = 2 * frecuencia de 2 segundo personaje.
Ejemplo:
Entrada: str[] = “aaaabbc”
Salida: Sí
Explicación: La substring str[0… 5] = “aaaabb” de la string dada se compone de solo dos caracteres ‘a’ y ‘b’ y la frecuencia de ‘a’ = 2 * frecuencia de ‘b’, es decir, 4 = 2 * 2. Otro ejemplo de una substring válida es str[4… 6] = “bbc”.Entrada: str[] = “abcdefg”
Salida: No
Enfoque ingenuo: el problema dado se puede resolver iterando sobre todas las substrings de la string dada y verificando si la string se compone de solo dos caracteres y la frecuencia del primer carácter = 2 * frecuencia del segundo carácter .
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando una técnica codiciosa . Al observar detenidamente, se puede notar que para que cualquier substring sea válida, debe existir una substring de tamaño 3 de esa string tal que esté compuesta por solo dos caracteres y la frecuencia del 1er carácter = 2 * frecuencia de el 2º carácter . _ Por lo tanto, el problema dado se puede resolver iterando a través de la string dada y para cada substring de longitud 3 , verifique si existe una string de la forma » xxy «, » xyx » o » yxx «.
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;
// Function to check if there exist a
// substring such that it is made up of
// only two characters and freq of 1st
// char is equal to 2 * freq of 2nd char
bool isPossible(string str)
{
// Loop to iterate over the string
for (int i = 0; i + 2 < str.size(); i++) {
// If the string is of
// the form "xxy"
if (str[i] == str[i + 1]
&& str[i] != str[i + 2]) {
return true;
}
// If the string is of
// the form "xyx"
if (str[i] == str[i + 2]
&& str[i] != str[i + 1]) {
return true;
}
// If the string is of
// the form "yxx"
if (str[i + 1] == str[i + 2]
&& str[i] != str[i + 1]) {
return true;
}
}
// If no valid substring exist
return false;
}
// Driver Code
int main()
{
string str = "aaaabbc";
if (isPossible(str))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program for the above approach
class GFG {
// Function to check if there exist a
// substring such that it is made up of
// only two characters and freq of 1st
// char is equal to 2 * freq of 2nd char
public static boolean isPossible(String str)
{
// Loop to iterate over the string
for (int i = 0; i + 2 < str.length(); i++) {
// If the string is of
// the form "xxy"
if (str.charAt(i) == str.charAt(i + 1)
&& str.charAt(i) != str.charAt(i + 2)) {
return true;
}
// If the string is of
// the form "xyx"
if (str.charAt(i) == str.charAt(i + 2)
&& str.charAt(i) != str.charAt(i + 1)) {
return true;
}
// If the string is of
// the form "yxx"
if (str.charAt(i + 1) == str.charAt(i + 2)
&& str.charAt(i) != str.charAt(i + 1)) {
return true;
}
}
// If no valid substring exist
return false;
}
// Driver Code
public static void main(String args[]) {
String str = "aaaabbc";
if (isPossible(str))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# Python3 program for the above approach
# Function to check if there exist a
# substring such that it is made up of
# only two characters and freq of 1st
# char is equal to 2 * freq of 2nd char
def isPossible(str):
# Loop to iterate over the string
for i in range(0, len(str) - 2):
# If the string is of
# the form "xxy"
if (str[i] == str[i + 1] and
str[i] != str[i + 2]):
return True
# If the string is of
# the form "xyx"
if (str[i] == str[i + 2] and
str[i] != str[i + 1]):
return True
# If the string is of
# the form "yxx"
if (str[i + 1] == str[i + 2] and
str[i] != str[i + 1]):
return True
# If no valid substring exist
return False
# Driver Code
if __name__ == "__main__":
str = "aaaabbc"
if (isPossible(str)):
print("Yes")
else:
print("No")
# This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
class GFG
{
// Function to check if there exist a
// substring such that it is made up of
// only two characters and freq of 1st
// char is equal to 2 * freq of 2nd char
public static bool isPossible(String str)
{
// Loop to iterate over the string
for (int i = 0; i + 2 < str.Length; i++)
{
// If the string is of
// the form "xxy"
if (str[i] == str[i + 1]
&& str[i] != str[i + 2])
{
return true;
}
// If the string is of
// the form "xyx"
if (str[i] == str[i + 2]
&& str[i] != str[i + 1])
{
return true;
}
// If the string is of
// the form "yxx"
if (str[i + 1] == str[i + 2]
&& str[i] != str[i + 1])
{
return true;
}
}
// If no valid substring exist
return false;
}
// Driver Code
public static void Main()
{
String str = "aaaabbc";
if (isPossible(str))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by saurabh_jaiswal.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to check if there exist a
// substring such that it is made up of
// only two characters and freq of 1st
// char is equal to 2 * freq of 2nd char
function isPossible( str)
{
// Loop to iterate over the string
for (let i = 0; i + 2 < str.length; i++) {
// If the string is of
// the form "xxy"
if (str[i] == str[i + 1]
&& str[i] != str[i + 2]) {
return true;
}
// If the string is of
// the form "xyx"
if (str[i] == str[i + 2]
&& str[i] != str[i + 1]) {
return true;
}
// If the string is of
// the form "yxx"
if (str[i + 1] == str[i + 2]
&& str[i] != str[i + 1]) {
return true;
}
}
// If no valid substring exist
return false;
}
// Driver Code
let str = "aaaabbc";
if (isPossible(str))
document.write("Yes");
else
document.write("No");
// This code is contributed by Potta Lokesh
</script>
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shaikhamaan3786 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA