Dadas dos strings S1 , S2 de longitud N y M respectivamente, y dos números enteros positivos N1 y N2 , la tarea es encontrar el recuento máximo de subsecuencias no superpuestas de S1 que son iguales a S2 concatenando la string s1 , n1 veces y la string s2 , n2 veces.
Ejemplos:
Entrada: S1 = “acb”, S2 = “ab”, N1 = 4, N2 = 2
Salida: 2
Explicación:
Concatenar la string S1, N1 (= 4) veces modifica S1 a “acbacbacbacb”.
Concatenar la string S2, N2 ( = 2) veces modifica S2 a «abab».
Dado que la string S2 aparece dos veces como una subsecuencia no superpuesta en S1, la salida requerida es 2.Entrada: S1 = “abc”, S2 = “a”, N1 = 1, N2 = 1
Salida: 1
Enfoque: el problema se puede resolver utilizando el concepto de verificar si una string es una subsecuencia de otra string o no .
Siga los pasos a continuación para resolver el problema:
- Itere sobre los caracteres de la string S2 y verifique si todos los caracteres de S2 están presentes en la string S1 o no. Si se encuentra que es falso, entonces no es posible tal subsecuencia de S1 que pueda hacerse igual a S2 concatenando la string S1 , N1 veces y la string S2 , N2 veces.
- Iterar sobre los caracteres de la string S1 , N1 veces circularmente. Para cada i -ésimo índice, compruebe si existe alguna subsecuencia de S1 hasta el i -ésimo índice, que es igual o no a S2 . Si se encuentra que es cierto, entonces incremente el conteo.
- Finalmente, imprima el conteo obtenido dividido por N2 como la respuesta requerida, luego de realizar las operaciones anteriores.
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 count maximum number of
// occurrences of s2 as subsequence in s1
// by concatenating s1, n1 times and s2, n2 times
int getMaxRepetitions(string s1, int n1,
string s2, int n2)
{
int temp1[26] = {0}, temp2[26] = {0};
for(char i:s1) temp1[i - 'a']++;
for(char i:s2) temp2[i - 'a']++;
for(int i = 0; i < 26; i++)
{
if(temp2[i] > temp1[i]) return 0;
}
// Stores number of times
// s1 is traversed
int s1_reps = 0;
// Stores number of times
// s2 is traversed
int s2_reps = 0;
// Mapping index of s2 to number
// of times s1 and s2 are traversed
map<int, pair<int, int> > s2_index_to_reps;
s2_index_to_reps[0] = {0, 0};
// Stores index of s1 circularly
int i = 0;
// Stores index of s2 circularly
int j = 0;
// Traverse the string s1, n1 times
while (s1_reps < n1){
// If current character of both
// the string are equal
if (s1[i] == s2[j])
// Update j
j += 1;
// Update i
i += 1;
// If j is length of s2
if (j == s2.size())
{
// Update j for
// circular traversal
j = 0;
// Update s2_reps
s2_reps += 1;
}
// If i is length of s1
if (i == s1.size())
{
// Update i for
// circular traversal
i = 0;
// Update s1_reps
s1_reps += 1;
// If already mapped j
// to (s1_reps, s2_reps)
if (s2_index_to_reps.find(j) !=
s2_index_to_reps.end())
break;
// Mapping j to (s1_reps, s2_reps)
s2_index_to_reps[j] = {s1_reps, s2_reps};
}
}
// If s1 already traversed n1 times
if (s1_reps == n1)
return s2_reps / n2;
// Otherwise, traverse string s1 by multiple of
// s1_reps and update both s1_reps and s2_reps
int initial_s1_reps = s2_index_to_reps[j].first ,
initial_s2_reps = s2_index_to_reps[j].second;
int loop_s1_reps = s1_reps - initial_s1_reps;
int loop_s2_reps = s2_reps - initial_s2_reps;
int loops = (n1 - initial_s1_reps);
// Update s2_reps
s2_reps = initial_s2_reps + loops * loop_s2_reps;
// Update s1_reps
s1_reps = initial_s1_reps + loops * loop_s1_reps;
// If s1 is traversed less than n1 times
while (s1_reps < n1)
{
// If current character in both
// the string are equal
if (s1[i] == s2[j])
// Update j
j += 1;
// Update i
i += 1;
// If i is length of s1
if (i == s1.size())
{
// Update i for circular traversal
i = 0;
// Update s1_reps
s1_reps += 1;
}
// If j is length of ss
if (j == s2.size())
{
// Update j for circular traversal
j = 0;
// Update s2_reps
s2_reps += 1;
}
}
return s2_reps / n2;
}
// Driver Code
int main()
{
string s1 = "acb";
int n1 = 4;
string s2 = "ab";
int n2 = 2;
cout << (getMaxRepetitions(s1, n1, s2, n2));
return 0;
}
// This code is contributed by mohit kumar 29.
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to count maximum number of
// occurrences of s2 as subsequence in s1
// by concatenating s1, n1 times and s2, n2 times
static int getMaxRepetitions(String s1, int n1,
String s2, int n2)
{
int temp1[] = new int[26], temp2[] = new int[26];
for(char i : s1.toCharArray())
temp1[i - 'a']++;
for(char i : s2.toCharArray())
temp2[i - 'a']++;
for(int i = 0; i < 26; i++)
{
if (temp2[i] > temp1[i])
return 0;
}
// Stores number of times
// s1 is traversed
int s1_reps = 0;
// Stores number of times
// s2 is traversed
int s2_reps = 0;
// Mapping index of s2 to number
// of times s1 and s2 are traversed
HashMap<Integer, int[]> s2_index_to_reps = new HashMap<>();
s2_index_to_reps.put(0, new int[] { 0, 0 });
// Stores index of s1 circularly
int i = 0;
// Stores index of s2 circularly
int j = 0;
// Traverse the string s1, n1 times
while (s1_reps < n1)
{
// If current character of both
// the string are equal
if (s1.charAt(i) == s2.charAt(j))
// Update j
j += 1;
// Update i
i += 1;
// If j is length of s2
if (j == s2.length())
{
// Update j for
// circular traversal
j = 0;
// Update s2_reps
s2_reps += 1;
}
// If i is length of s1
if (i == s1.length())
{
// Update i for
// circular traversal
i = 0;
// Update s1_reps
s1_reps += 1;
// If already mapped j
// to (s1_reps, s2_reps)
if (!s2_index_to_reps.containsKey(j))
break;
// Mapping j to (s1_reps, s2_reps)
s2_index_to_reps.put(
j, new int[] { s1_reps, s2_reps });
}
}
// If s1 already traversed n1 times
if (s1_reps == n1)
return s2_reps / n2;
// Otherwise, traverse string s1 by multiple of
// s1_reps and update both s1_reps and s2_reps
int initial_s1_reps = s2_index_to_reps.get(j)[0],
initial_s2_reps = s2_index_to_reps.get(j)[1];
int loop_s1_reps = s1_reps - initial_s1_reps;
int loop_s2_reps = s2_reps - initial_s2_reps;
int loops = (n1 - initial_s1_reps);
// Update s2_reps
s2_reps = initial_s2_reps + loops * loop_s2_reps;
// Update s1_reps
s1_reps = initial_s1_reps + loops * loop_s1_reps;
// If s1 is traversed less than n1 times
while (s1_reps < n1)
{
// If current character in both
// the string are equal
if (s1.charAt(i) == s2.charAt(j))
// Update j
j += 1;
// Update i
i += 1;
// If i is length of s1
if (i == s1.length())
{
// Update i for circular traversal
i = 0;
// Update s1_reps
s1_reps += 1;
}
// If j is length of ss
if (j == s2.length())
{
// Update j for circular traversal
j = 0;
// Update s2_reps
s2_reps += 1;
}
}
return s2_reps / n2;
}
// Driver Code
public static void main(String[] args)
{
String s1 = "acb";
int n1 = 4;
String s2 = "ab";
int n2 = 2;
System.out.println(
getMaxRepetitions(s1, n1, s2, n2));
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
# Function to count maximum number of
# occurrences of s2 as subsequence in s1
# by concatenating s1, n1 times and s2, n2 times
def getMaxRepetitions(s1, n1, s2, n2):
# If all the characters of s2 are not present in s1
if any(c for c in set(s2) if c not in set(s1)):
return 0
# Stores number of times
# s1 is traversed
s1_reps = 0
# Stores number of times
# s2 is traversed
s2_reps = 0
# Mapping index of s2 to number
# of times s1 and s2 are traversed
s2_index_to_reps = { 0 : (0, 0)}
# Stores index of s1 circularly
i = 0
# Stores index of s2 circularly
j = 0
# Traverse the string s1, n1 times
while s1_reps < n1:
# If current character of both
# the string are equal
if s1[i] == s2[j]:
# Update j
j += 1
# Update i
i += 1
# If j is length of s2
if j == len(s2):
# Update j for
# circular traversal
j = 0
# Update s2_reps
s2_reps += 1
# If i is length of s1
if i == len(s1):
# Update i for
# circular traversal
i = 0
# Update s1_reps
s1_reps += 1
# If already mapped j
# to (s1_reps, s2_reps)
if j in s2_index_to_reps:
break
# Mapping j to (s1_reps, s2_reps)
s2_index_to_reps[j] = (s1_reps, s2_reps)
# If s1 already traversed n1 times
if s1_reps == n1:
return s2_reps // n2
# Otherwise, traverse string s1 by multiple of
# s1_reps and update both s1_reps and s2_reps
initial_s1_reps, initial_s2_reps = s2_index_to_reps[j]
loop_s1_reps = s1_reps - initial_s1_reps
loop_s2_reps = s2_reps - initial_s2_reps
loops = (n1 - initial_s1_reps)
# Update s2_reps
s2_reps = initial_s2_reps + loops * loop_s2_reps
# Update s1_reps
s1_reps = initial_s1_reps + loops * loop_s1_reps
# If s1 is traversed less than n1 times
while s1_reps < n1:
# If current character in both
# the string are equal
if s1[i] == s2[j]:
# Update j
j += 1
# Update i
i += 1
# If i is length of s1
if i == len(s1):
# Update i for circular traversal
i = 0
# Update s1_reps
s1_reps += 1
# If j is length of ss
if j == len(s2):
# Update j for circular traversal
j = 0
# Update s2_reps
s2_reps += 1
return s2_reps // n2
# Driver Code
if __name__ == '__main__':
s1 = "acb"
n1 = 4
s2 = "ab"
n2 = 2
print(getMaxRepetitions(s1, n1, s2, n2))
Javascript
<script>
// Javascript program for the above approach
// Function to count maximum number of
// occurrences of s2 as subsequence in s1
// by concatenating s1, n1 times and s2, n2 times
function getMaxRepetitions(s1,n1,s2,n2)
{
let temp1 = new Array(26);
let temp2 = new Array(26);
for(let i = 0; i < 26; i++)
{
temp1[i] = 0;
temp2[i] = 0;
}
for(let i = 0; i < s1.split("").length; i++)
temp1[s1[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
for(let i = 0; i < s2.split("").length; i++)
temp2[s2[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
for(let i = 0; i < 26; i++)
{
if (temp2[i] > temp1[i])
return 0;
}
// Stores number of times
// s1 is traversed
let s1_reps = 0;
// Stores number of times
// s2 is traversed
let s2_reps = 0;
// Mapping index of s2 to number
// of times s1 and s2 are traversed
let s2_index_to_reps = new Map();
s2_index_to_reps.set(0, [ 0, 0 ]);
// Stores index of s1 circularly
let i = 0;
// Stores index of s2 circularly
let j = 0;
// Traverse the string s1, n1 times
while (s1_reps < n1)
{
// If current character of both
// the string are equal
if (s1[i] == s2[j])
// Update j
j += 1;
// Update i
i += 1;
// If j is length of s2
if (j == s2.length)
{
// Update j for
// circular traversal
j = 0;
// Update s2_reps
s2_reps += 1;
}
// If i is length of s1
if (i == s1.length)
{
// Update i for
// circular traversal
i = 0;
// Update s1_reps
s1_reps += 1;
// If already mapped j
// to (s1_reps, s2_reps)
if (!s2_index_to_reps.has(j))
break;
// Mapping j to (s1_reps, s2_reps)
s2_index_to_reps.set(
j, [s1_reps, s2_reps ]);
}
}
// If s1 already traversed n1 times
if (s1_reps == n1)
return s2_reps / n2;
// Otherwise, traverse string s1 by multiple of
// s1_reps and update both s1_reps and s2_reps
let initial_s1_reps = s2_index_to_reps.get(j)[0],
initial_s2_reps = s2_index_to_reps.get(j)[1];
let loop_s1_reps = s1_reps - initial_s1_reps;
let loop_s2_reps = s2_reps - initial_s2_reps;
let loops = (n1 - initial_s1_reps);
// Update s2_reps
s2_reps = initial_s2_reps + loops * loop_s2_reps;
// Update s1_reps
s1_reps = initial_s1_reps + loops * loop_s1_reps;
// If s1 is traversed less than n1 times
while (s1_reps < n1)
{
// If current character in both
// the string are equal
if (s1[i] == s2[j])
// Update j
j += 1;
// Update i
i += 1;
// If i is length of s1
if (i == s1.length)
{
// Update i for circular traversal
i = 0;
// Update s1_reps
s1_reps += 1;
}
// If j is length of ss
if (j == s2.length)
{
// Update j for circular traversal
j = 0;
// Update s2_reps
s2_reps += 1;
}
}
return s2_reps / n2;
}
// Driver Code
let s1 = "acb";
let n1 = 4;
let s2 = "ab";
let n2 = 2;
document.write(getMaxRepetitions(s1, n1, s2, n2));
// This code is contributed by unknown2108
</script>
Producción:
2
Complejidad de Tiempo: O((N + M) * n1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA