Dada una string str que consta de dígitos, la tarea es encontrar el número de posibles subsecuencias de 4 dígitos que tienen la forma (x, x, x + 1, x + 1) donde x puede estar en el rango [0, 8] .
Ejemplos:
Entrada: str = “1122”
Salida: 1
Solo una subsecuencia es válida, es decir, la string completa.
Entrada: str = “13134422”
Salida: 2
Dos subsecuencias válidas están presentes “1122” y “3344”.
Acercarse:
- Encontraremos el número total de posibles subsecuencias para cada posible x de 0 a 8.
- Para cada x, elimine todos los demás dígitos de la string, excepto x y x+1, ya que no afectan la respuesta.
- Mantenga una array de suma de prefijos para contar el número de x+1 dígitos hasta el i-ésimo índice en la string.
- Ahora, para cada club de dígitos digamos tamaño K (que son x), podemos elegir dos números en formas KC2. Los últimos dos números pueden ser dos números cualesquiera de todos los dígitos (que son x+1) que siguen a ese club de dígitos (el conteo se determina usando Prefix Sum Array) digamos tamaño L, por lo que hay LC2 formas de elegir. Vías Totales = KC2 * LC2 .
- Hasta ahora, podemos considerar que x proviene del mismo club, pero también puede ser de varios clubes. Por lo tanto, tenemos que considerar todos los pares de tréboles posibles y multiplicar su tamaño para obtener el número de formas de elegir los dos primeros números. Para los dos últimos números, las formas seguirán siendo las mismas.
- Para evitar el problema de contar en exceso en el Paso 5, solo se elegirá la forma posible que incluya el palo actual en consideración, ya que otras ya se han considerado en el cálculo de los palos anteriores.
- Sume todas las formas posibles para todos los valores de x y tome Modulo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
using namespace std;
// Function to return the total
// required sub-sequences
int solve(string test)
{
int size = test.size();
int total = 0;
// Find ways for all values of x
for (int i = 0; i <= 8; i++) {
int x = i;
// x+1
int y = i + 1;
string newtest;
// Removing all unnecessary digits
for (int j = 0; j < size; j++) {
if (test[j] == x + 48 || test[j] == y + 48) {
newtest += test[j];
}
}
if (newtest.size() > 0) {
int size1 = newtest.size();
// Prefix Sum Array for X+1 digit
int prefix[size1] = { 0 };
for (int j = 0; j < size1; j++) {
if (newtest[j] == y + 48) {
prefix[j]++;
}
}
for (int j = 1; j < size1; j++) {
prefix[j] += prefix[j - 1];
}
int count = 0;
int firstcount = 0;
// Sum of squares
int ss = 0;
// Previous sum of all possible pairs
int prev = 0;
for (int j = 0; j < size1; j++) {
if (newtest[j] == x + 48) {
count++;
firstcount++;
}
else {
ss += count * count;
// To find sum of multiplication of all
// possible pairs
int pairsum = (firstcount * firstcount - ss) / 2;
int temp = pairsum;
// To prevent overcounting
pairsum -= prev;
prev = temp;
int secondway = prefix[size1 - 1];
if (j != 0)
secondway -= prefix[j - 1];
int answer = count * (count - 1)
* secondway * (secondway - 1);
answer /= 4;
answer += (pairsum * secondway
* (secondway - 1)) / 2;
// Adding ways for all possible x
total += answer;
count = 0;
}
}
}
}
return total;
}
// Driver code
int main()
{
string test = "13134422";
cout << solve(test) << endl;
return 0;
}
Java
// Java Implementation of above approach
import java.io.*;
class GFG
{
// Function to return the total
// required sub-sequences
static int solve(String test, int MOD)
{
int size = test.length();
int total = 0;
// Find ways for all values of x
for (int i = 0; i <= 8; i++)
{
int x = i;
// x+1
int y = i + 1;
String newtest = "";
// Removing all unnecessary digits
for (int j = 0; j < size; j++)
{
if (test.charAt(j) == x + 48 || test.charAt(j) == y + 48)
{
newtest += test.charAt(j);
}
}
if (newtest.length() > 0) {
int size1 = newtest.length();
// Prefix Sum Array for X+1 digit
int []prefix = new int[size1];
for (int j = 0; j < size1; j++)
{
prefix[j] = 0;
if (newtest.charAt(j) == y + 48)
{
prefix[j]++;
}
}
for (int j = 1; j < size1; j++)
{
prefix[j] += prefix[j - 1];
}
int count = 0;
int firstcount = 0;
// Sum of squares
int ss = 0;
// Previous sum of all possible pairs
int prev = 0;
for (int j = 0; j < size1; j++)
{
if (newtest.charAt(j) == x + 48)
{
count++;
firstcount++;
}
else
{
ss += count * count;
// To find sum of multiplication of all
// possible pairs
int pairsum = (firstcount * firstcount - ss) / 2;
int temp = pairsum;
// To prevent overcounting
pairsum -= prev;
prev = temp;
int secondway = prefix[size1 - 1];
if (j != 0)
secondway -= prefix[j - 1];
int answer = count * (count - 1)
* secondway * (secondway - 1);
answer /= 4;
answer += (pairsum * secondway
* (secondway - 1)) / 2;
// Adding ways for all possible x
total += answer;
count = 0;
}
}
}
}
return total;
}
// Driver code
public static void main (String[] args)
{
String test = "13134422";
int MOD = 1000000007;
System.out.println(solve(test,MOD));
}
}
// This code is contributed by krikti..
Python3
# Python3 implementation of the approach MOD= 1000000007 # Function to return the total # required sub-sequences def solve(test): size = len(test) total = 0 # Find ways for all values of x for i in range(9): x = i # x+1 y = i + 1 newtest="" # Removing all unnecessary digits for j in range(size): if (ord(test[j]) == x + 48 or ord(test[j]) == y + 48): newtest += test[j] if (len(newtest) > 0): size1 = len(newtest) # Prefix Sum Array for X+1 digit prefix=[0 for i in range(size1)] for j in range(size1): if (ord(newtest[j]) == y + 48): prefix[j]+=1 for j in range(1,size1): prefix[j] += prefix[j - 1] count = 0 firstcount = 0 # Sum of squares ss = 0 # Previous sum of all possible pairs prev = 0 for j in range(size1): if (ord(newtest[j]) == x + 48): count+=1 firstcount+=1 else: ss += count * count # To find sum of multiplication of all # possible pairs pairsum = (firstcount * firstcount - ss) // 2 temp = pairsum # To prevent overcounting pairsum -= prev prev = temp secondway = prefix[size1 - 1] if (j != 0): secondway -= prefix[j - 1] answer = count * (count - 1)* secondway * (secondway - 1) answer //= 4 answer += (pairsum * secondway * (secondway - 1)) // 2 # Adding ways for all possible x total += answer count = 0 return total # Driver code test = "13134422" print(solve(test)) # This code is contributed by mohit kumar 29
C#
// C# Implementation of above approach
using System;
class GFG
{
// Function to return the total
// required sub-sequences
static int solve(string test, int MOD)
{
int size = test.Length;
int total = 0;
// Find ways for all values of x
for (int i = 0; i <= 8; i++)
{
int x = i;
// x+1
int y = i + 1;
string newtest = "";
// Removing all unnecessary digits
for (int j = 0; j < size; j++)
{
if (test[j] == x + 48 || test[j] == y + 48)
{
newtest += test[j];
}
}
if (newtest.Length > 0) {
int size1 = newtest.Length;
// Prefix Sum Array for X+1 digit
int []prefix = new int[size1];
for (int j = 0; j < size1; j++)
{
prefix[j] = 0;
if (newtest[j] == y + 48)
{
prefix[j]++;
}
}
for (int j = 1; j < size1; j++)
{
prefix[j] += prefix[j - 1];
}
int count = 0;
int firstcount = 0;
// Sum of squares
int ss = 0;
// Previous sum of all possible pairs
int prev = 0;
for (int j = 0; j < size1; j++)
{
if (newtest[j] == x + 48)
{
count++;
firstcount++;
}
else
{
ss += count * count;
// To find sum of multiplication of all
// possible pairs
int pairsum = (firstcount * firstcount - ss) / 2;
int temp = pairsum;
// To prevent overcounting
pairsum -= prev;
prev = temp;
int secondway = prefix[size1 - 1];
if (j != 0)
secondway -= prefix[j - 1];
int answer = count * (count - 1)
* secondway * (secondway - 1);
answer /= 4;
answer += (pairsum * secondway
* (secondway - 1)) / 2;
// Adding ways for all possible x
total += answer;
count = 0;
}
}
}
}
return total;
}
// Driver code
public static void Main ()
{
string test = "13134422";
int MOD = 1000000007;
Console.WriteLine(solve(test,MOD));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript Implementation of above approach
// Function to return the total
// required sub-sequences
function solve(test,MOD)
{
let size = test.length;
let total = 0;
// Find ways for all values of x
for (let i = 0; i <= 8; i++)
{
let x = i;
// x+1
let y = i + 1;
let newtest = "";
// Removing all unnecessary digits
for (let j = 0; j < size; j++)
{
if (test[j].charCodeAt(0) == x + 48 ||
test[j].charCodeAt(0) == y + 48)
{
newtest += test[j];
}
}
if (newtest.length > 0) {
let size1 = newtest.length;
// Prefix Sum Array for X+1 digit
let prefix = new Array(size1);
for (let j = 0; j < size1; j++)
{
prefix[j] = 0;
if (newtest[j].charCodeAt(0) == y + 48)
{
prefix[j]++;
}
}
for (let j = 1; j < size1; j++)
{
prefix[j] += prefix[j - 1];
}
let count = 0;
let firstcount = 0;
// Sum of squares
let ss = 0;
// Previous sum of all possible pairs
let prev = 0;
for (let j = 0; j < size1; j++)
{
if (newtest[j].charCodeAt(0) == x + 48)
{
count++;
firstcount++;
}
else
{
ss += count * count;
// To find sum of multiplication of all
// possible pairs
let pairsum =
Math.floor((firstcount * firstcount - ss) / 2);
let temp = pairsum;
// To prevent overcounting
pairsum -= prev;
prev = temp;
let secondway = prefix[size1 - 1];
if (j != 0)
secondway -= prefix[j - 1];
let answer = count * (count - 1)
* secondway * (secondway - 1);
answer = Math.floor(answer/4);
answer += Math.floor((pairsum * secondway
* (secondway - 1)) / 2);
// Adding ways for all possible x
total += answer;
count = 0;
}
}
}
}
return total;
}
// Driver code
let test = "13134422";
let MOD = 1000000007;
document.write(solve(test,MOD));
// This code is contributed by unknown2108
</script>
Producción:
2