Dada una string de longitud n y una subsecuencia de longitud 3. Encuentra el número total de ocurrencias de la subsecuencia en esta string.
Ejemplos:
Input : string = "GFGFGYSYIOIWIN",
subsequence = "GFG"
Output : 4
Explanation : There are 4 such subsequences as shown:
GFGFGYSYIOIWIN
GFGFGYSYIOIWIN
GFGFGYSYIOIWIN
GFGFGYSYIOIWIN
Input : string = "GFGGGZZYNOIWIN",
subsequence = "GFG"
Output : 3
Enfoque de fuerza bruta : la forma más sencilla de resolver este problema es ejecutar tres bucles para los caracteres del árbol de las subsecuencias dadas. Eso inicia un ciclo para encontrar el primer carácter de la subsecuencia en la string, una vez que se encuentra este carácter, se inicia un ciclo después de este índice para encontrar el segundo carácter, una vez que se encuentra este carácter, se inicia un ciclo después de este índice para encontrar el tercer carácter. Mantener una variable para almacenar el número de ocurrencias del tercer carácter, es decir, el número de ocurrencias de la subsecuencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find number of occurrences of
// a subsequence of length 3
#include<iostream>
using namespace std;
// Function to find number of occurrences of
// a subsequence of length three in a string
int findOccurrences(string str, string substr)
{
// variable to store no of occurrences
int counter = 0;
// loop to find first character
for (int i=0;i<str.length();i++)
{
if (str[i]==substr[0])
{
// loop to find 2nd character
for (int j=i+1;j<str.length();j++)
{
if (str[j]==substr[1])
{
// loop to find 3rd character
for (int k = j+1; k<str.length(); k++)
{
// increment count if subsequence
// is found
if (str[k]==substr[2])
counter++;
}
}
}
}
}
return counter;
}
// Driver code
int main()
{
string str = "GFGFGYSYIOIWIN";
string substr = "GFG";
cout << findOccurrences(str, substr);
return 0;
}
Java
// Java program to find number of occurrences of
// a subsequence of length 3
import java.util.*;
import java.lang.*;
public class GfG{
// Function to find number of occurrences of
// a subsequence of length three in a string
public static int findOccurrences(String str1, String substr1)
{
// variable to store no of occurrences
int counter = 0;
char[] str = str1.toCharArray();
char[] substr = substr1.toCharArray();
// loop to find first character
for (int i=0; i < str1.length(); i++)
{
if (str[i] == substr[0])
{
// loop to find 2nd character
for (int j = i+1; j < str1.length(); j++)
{
if (str[j] == substr[1])
{
// loop to find 3rd character
for (int k = j+1; k < str1.length(); k++)
{
// increment count if subsequence
// is found
if (str[k] == substr[2])
counter++;
}
}
}
}
}
return counter;
}
// Driver function
public static void main(String argc[]){
String str = "GFGFGYSYIOIWIN";
String substr = "GFG";
System.out.println(findOccurrences(str, substr));
}
}
/* This code is contributed by Sagar Shukla */
Python3
# Python program to find # number of occurrences # of a subsequence of # length 3 # Function to find number # of occurrences of a # subsequence of length # three in a string def findOccurrences(str, substr) : # variable to store # no of occurrences counter = 0 # loop to find # first character for i in range(0, len(str)) : if (str[i] == substr[0]) : # loop to find # 2nd character for j in range(i + 1, len(str)) : if (str[j] == substr[1]) : # loop to find # 3rd character for k in range(j + 1, len(str)) : # increment count if # subsequence is found if (str[k] == substr[2]) : counter = counter + 1 return counter # Driver Code str = "GFGFGYSYIOIWIN" substr = "GFG" print (findOccurrences(str, substr)) # This code is contributed by # Manish Shaw(manishshaw1)
C#
// C# program to find number of occurrences of
// a subsequence of length 3
using System;
public class GfG {
// Function to find number of occurrences of
// a subsequence of length three in a string
public static int findOccurrences(string str1,
string substr1)
{
// variable to store no of occurrences
int counter = 0;
//char[] str = str1.toCharArray();
//char[] substr = substr1.toCharArray();
// loop to find first character
for (int i=0; i < str1.Length; i++)
{
if (str1[i] == substr1[0])
{
// loop to find 2nd character
for (int j = i+1; j < str1.Length; j++)
{
if (str1[j] == substr1[1])
{
// loop to find 3rd character
for (int k = j+1; k < str1.Length; k++)
{
// increment count if subsequence
// is found
if (str1[k] == substr1[2])
counter++;
}
}
}
}
}
return counter;
}
// Driver function
public static void Main()
{
string str1 = "GFGFGYSYIOIWIN";
string substr1 = "GFG";
Console.WriteLine(findOccurrences(str1, substr1));
}
}
/* This code is contributed by vt_m */
PHP
<?php
// PHP program to find number
// of occurrences of a
// subsequence of length 3
// Function to find number of
// occurrences of a subsequence
// of length three in a string
function findOccurrences($str, $substr)
{
// variable to store
// no of occurrences
$counter = 0;
// loop to find first character
for ($i = 0;$i < strlen($str); $i++)
{
if ($str[$i] == $substr[0])
{
// loop to find 2nd character
for ($j = $i + 1; $j < strlen($str); $j++)
{
if ($str[$j] == $substr[1])
{
// loop to find 3rd character
for ($k = $j + 1; $k < strlen($str); $k++)
{
// increment count if
// subsequence is found
if ($str[$k] == $substr[2])
$counter++;
}
}
}
}
}
return $counter;
}
// Driver Code
$str = "GFGFGYSYIOIWIN";
$substr = "GFG";
echo findOccurrences($str, $substr);
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program to find number
// of occurrences of a subsequence of length 3
// Function to find number of occurrences of
// a subsequence of length three in a string
function findOccurrences(str1, substr1)
{
// Variable to store no of occurrences
let counter = 0;
//char[] str = str1.toCharArray();
//char[] substr = substr1.toCharArray();
// Loop to find first character
for(let i = 0; i < str1.length; i++)
{
if (str1[i] == substr1[0])
{
// Loop to find 2nd character
for(let j = i + 1; j < str1.length; j++)
{
if (str1[j] == substr1[1])
{
// Loop to find 3rd character
for (let k = j + 1; k < str1.length; k++)
{
// Increment count if subsequence
// is found
if (str1[k] == substr1[2])
counter++;
}
}
}
}
}
return counter;
}
// Driver code
let str1 = "GFGFGYSYIOIWIN";
let substr1 = "GFG";
document.write(findOccurrences(str1, substr1));
// This code is contributed by suresh07
</script>
Producción :
4
Complejidad de tiempo: O(n^3)
Espacio auxiliar: O(1)
Enfoque eficiente : el método eficiente para resolver este problema es utilizar el concepto de cálculo previo. La idea es que, para cada aparición del carácter intermedio de la subsecuencia en la string, calcule previamente dos valores. Es decir, el número de ocurrencias del primer carácter anterior y el número de ocurrencias del tercer carácter posterior y multiplicar estos dos valores para generar el total de ocurrencias para cada ocurrencia del carácter central.
A continuación se muestra la implementación de esta idea:
C++
// C++ program to find number of occurrences of
// a subsequence of length 3
#include<iostream>
using namespace std;
// Function to find number of occurrences of
// a subsequence of length three in a string
int findOccurrences(string str, string substr)
{
// calculate length of string
int n = str.length();
// auxiliary array to store occurrences of
// first character
int preLeft[n] = {0};
// auxiliary array to store occurrences of
// third character
int preRight[n] = {0};
if (str[0]==substr[0])
preLeft[0]++;
// calculate occurrences of first character
// upto ith index from left
for (int i=1;i<n;i++)
{
if (str[i]==substr[0])
preLeft[i] = preLeft[i-1] + 1;
else
preLeft[i] = preLeft[i-1];
}
if (str[n-1]==substr[2])
preRight[n-1]++;
// calculate occurrences of third character
// upto ith index from right
for(int i=n-2;i>=0;i--)
{
if (str[i]==substr[2])
preRight[i] = preRight[i+1] + 1;
else
preRight[i] = preRight[i+1];
}
// variable to store total number of occurrences
int counter = 0;
// loop to find the occurrences of middle element
for (int i=1; i<n-1;i++)
{
// if middle character of subsequence is found
// in the string
if (str[i]==str[1])
{
// multiply the total occurrences of first
// character before middle character with
// the total occurrences of third character
// after middle character
int total = preLeft[i-1]*preRight[i+1];
counter += total;
}
}
return counter;
}
// Driver code
int main()
{
string str = "GFGFGYSYIOIWIN";
string substr = "GFG";
cout << findOccurrences(str,substr);
return 0;
}
Java
// Java program to find number of occurrences of
// a subsequence of length 3
import java.util.*;
import java.lang.*;
public class GfG{
// Function to find number of occurrences of
// a subsequence of length three in a string
public static int findOccurrences(String str1, String substr1)
{
// calculate length of string
int n = str1.length();
char[] str = str1.toCharArray();
char[] substr = substr1.toCharArray();
// auxiliary array to store occurrences of
// first character
int[] preLeft = new int[n];
// auxiliary array to store occurrences of
// third character
int[] preRight = new int[n];
if (str[0] == substr[0])
preLeft[0]++;
// calculate occurrences of first character
// upto ith index from left
for (int i = 1; i < n; i++)
{
if (str[i] == substr[0])
preLeft[i] = preLeft[i-1] + 1;
else
preLeft[i] = preLeft[i-1];
}
if (str[n-1] == substr[2])
preRight[n-1]++;
// calculate occurrences of third character
// upto ith index from right
for(int i = n-2; i >= 0; i--)
{
if (str[i] == substr[2])
preRight[i] = preRight[i+1] + 1;
else
preRight[i] = preRight[i+1];
}
// variable to store total number of occurrences
int counter = 0;
// loop to find the occurrences of middle element
for (int i = 1; i < n-1; i++)
{
// if middle character of subsequence is found
// in the string
if (str[i] == str[1])
{
// multiply the total occurrences of first
// character before middle character with
// the total occurrences of third character
// after middle character
int total = preLeft[i-1] * preRight[i+1];
counter += total;
}
}
return counter;
}
// Driver function
public static void main(String argc[]){
String str = "GFGFGYSYIOIWIN";
String substr = "GFG";
System.out.println(findOccurrences(str, substr));
}
/* This code is contributed by Sagar Shukla */
}
Python3
# Python 3 program to find number of # occurrences of a subsequence of length 3 # Function to find number of occurrences of # a subsequence of length three in a string def findOccurrences(str1, substr): # calculate length of string n = len(str1) # auxiliary array to store occurrences of # first character preLeft = [0 for i in range(n)] # auxiliary array to store occurrences of # third character preRight = [0 for i in range(n)] if (str1[0] == substr[0]): preLeft[0] += 1 # calculate occurrences of first character # upto ith index from left for i in range(1, n): if (str1[i] == substr[0]): preLeft[i] = preLeft[i - 1] + 1 else: preLeft[i] = preLeft[i - 1] if (str1[n - 1] == substr[2]): preRight[n - 1] += 1 # calculate occurrences of third character # upto ith index from right i = n - 2 while(i >= 0): if (str1[i] == substr[2]): preRight[i] = preRight[i + 1] + 1 else: preRight[i] = preRight[i + 1] i -= 1 # variable to store # total number of occurrences counter = 0 # loop to find the occurrences # of middle element for i in range(1, n - 1): # if middle character of subsequence # is found in the string if (str1[i] == str1[1]): # multiply the total occurrences of first # character before middle character with # the total occurrences of third character # after middle character total = preLeft[i - 1] * preRight[i + 1] counter += total return counter # Driver code if __name__ == '__main__': str1 = "GFGFGYSYIOIWIN" substr = "GFG" print(findOccurrences(str1, substr)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find number of occurrences of
// a subsequence of length 3
using System;
public class GfG {
// Function to find number of occurrences of
// a subsequence of length three in a string
public static int findOccurrences(string str1,
string substr1)
{
// calculate length of string
int n = str1.Length;
// char[] str = str1.toCharArray();
// char[] substr = substr1.toCharArray();
// auxiliary array to store occurrences of
// first character
int[] preLeft = new int[n];
// auxiliary array to store occurrences of
// third character
int[] preRight = new int[n];
if (str1[0] == substr1[0])
preLeft[0]++;
// calculate occurrences of first character
// upto ith index from left
for (int i = 1; i < n; i++)
{
if (str1[i] == substr1[0])
preLeft[i] = preLeft[i-1] + 1;
else
preLeft[i] = preLeft[i-1];
}
if (str1[n-1] == substr1[2])
preRight[n-1]++;
// calculate occurrences of third character
// upto ith index from right
for(int i = n-2; i >= 0; i--)
{
if (str1[i] == substr1[2])
preRight[i] = preRight[i+1] + 1;
else
preRight[i] = preRight[i+1];
}
// variable to store total number of occurrences
int counter = 0;
// loop to find the occurrences of middle element
for (int i = 1; i < n-1; i++)
{
// if middle character of subsequence is found
// in the string
if (str1[i] == str1[1])
{
// multiply the total occurrences of first
// character before middle character with
// the total occurrences of third character
// after middle character
int total = preLeft[i-1] * preRight[i+1];
counter += total;
}
}
return counter;
}
// Driver function
public static void Main()
{
string str1 = "GFGFGYSYIOIWIN";
string substr1 = "GFG";
Console.WriteLine(findOccurrences(str1, substr1));
}
}
/* This code is contributed by Vt_m */
PHP
<?php
// PHP program to find number
// of occurrences of a
// subsequence of length 3
// Function to find number
// of occurrences of a
// subsequence of length
// three in a string
function findOccurrences($str,
$substr)
{
// calculate length of string
$n = strlen($str);
// auxiliary array to store
// occurrences of first character
$preLeft = array(0);
// auxiliary array to store
// occurrences of third character
$preRight = array(0);
if ($str[0] == $substr[0])
$preLeft[0]++;
// calculate occurrences
// of first character
// upto ith index from left
for ($i = 1; $i < $n; $i++)
{
if ($str[$i] == $substr[0])
$preLeft[$i] = $preLeft[$i - 1] + 1;
else
$preLeft[$i] = $preLeft[$i - 1];
}
if ($str[$n - 1] == $substr[2])
$preRight[$n - 1]++;
// calculate occurrences
// of third character
// upto ith index from right
for($i = $n - 2; $i >= 0; $i--)
{
if ($str[$i] == $substr[2])
$preRight[$i] = ($preRight[$i + 1] + 1);
else
$preRight[$i] = $preRight[$i + 1];
}
// variable to store total
// number of occurrences
$counter = 0;
// loop to find the occurrences
// of middle element
for ($i = 1; $i < $n - 1; $i++)
{
// if middle character of
// subsequence is found
// in the string
if ($str[$i] == $str[1])
{
// multiply the total occurrences
// of first character before
// middle character with the
// total occurrences of third
// character after middle character
$total = $preLeft[$i - 1] *
$preRight[$i + 1];
$counter += $total;
}
}
return $counter;
}
// Driver Code
$str = "GFGFGYSYIOIWIN";
$substr = "GFG";
echo findOccurrences($str, $substr);
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program to find
// number of occurrences
// of a subsequence of length 3
// Function to find number of occurrences of
// a subsequence of length three in a string
function findOccurrences(str, substr)
{
// calculate length of string
let n = str.length;
// char[] str = str.toCharArray();
// char[] substr = substr.toCharArray();
// auxiliary array to store occurrences of
// first character
let preLeft = new Array(n);
preLeft.fill(0);
// auxiliary array to store occurrences of
// third character
let preRight = new Array(n);
preRight.fill(0);
if (str[0] == substr[0])
preLeft[0]++;
// calculate occurrences of first character
// upto ith index from left
for (let i = 1; i < n; i++)
{
if (str[i] == substr[0])
preLeft[i] = preLeft[i-1] + 1;
else
preLeft[i] = preLeft[i-1];
}
if (str[n-1] == substr[2])
preRight[n-1]++;
// calculate occurrences of third character
// upto ith index from right
for(let i = n-2; i >= 0; i--)
{
if (str[i] == substr[2])
preRight[i] = preRight[i+1] + 1;
else
preRight[i] = preRight[i+1];
}
// variable to store total
// number of occurrences
let counter = 0;
// loop to find the occurrences
// of middle element
for (let i = 1; i < n-1; i++)
{
// if middle character of subsequence
// is found
// in the string
if (str[i] == str[1])
{
// multiply the total
// occurrences of first
// character before middle
// character with
// the total occurrences
// of third character
// after middle character
let total = preLeft[i-1] * preRight[i+1];
counter += total;
}
}
return counter;
}
let str = "GFGFGYSYIOIWIN";
let substr = "GFG";
document.write(findOccurrences(str, substr));
</script>
Producción:
4
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por harsh.agarwal0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA