Dada una string numérica S de longitud N y un dígito K , la tarea es encontrar el número máximo de strings distintas que tengan una aparición máxima de K formada al reemplazar dos dígitos adyacentes de S con K si su suma es K .
Ejemplos:
Entrada: S = “313”, K = 4
Salida: 2
Explicación: Las posibles strings que se pueden generar son:
- Reemplazar S[0] y S[1] con K modifica S a «43».
- Reemplazar S[1] y S[2] con K modifica S a «34».
Entrada: S = “12352”, K = 7
Salida: 1
Explicación: La única string posible es reemplazando S[3] y S[4] con K, es decir, S = “1237”.
Enfoque: El problema dado se puede resolver utilizando la observación de que para alguna substring de S , hay dos tipos de posibilidad de contribuir al resultado, es decir, puede ser una secuencia de «xy» que tenga un número igual de x y y , es decir, “xyxy…xyxy” o puede ser una secuencia de xy que tiene una x adicional , es decir, “xyxy…xyxyx” donde x + y = K .
- Caso 1: La string de la forma “xyxy…xyxy” se puede convertir a la string “KK…KK” dondeaparece K (longitud de la substring)/2 veces. Entonces, el número de strings distintas que se formarán es 1 .
- Caso 2: La string de la forma “xyxy…xyxyx” tiene una ‘x’ extra y se puede convertir en la string “KK…KKx” dondeaparece K (longitud de la substring-1)/2 veces. Sea estevalor M. Tras la observación, se puede ver que habrá (M + 1) posiciones posibles para x en la string convertida.
Siga los pasos a continuación para resolver el problema:
- Inicialice las variables ans con 1 , flag con 0 y start_index con -1 donde ans almacenará la respuesta hasta el índice i y start_index se usará para almacenar el índice inicial de cada substring desde donde comenzó la secuencia deseada.
- Atraviesa la cuerda S y haz lo siguiente:
- Si la suma de los dígitos adyacentes S[i] y S[i + 1] es K y flag se establece en false , establezca flag en true y start_index en i .
- Si la bandera es verdadera y S[i] y S[i + 1] no es K , establezca la bandera en falso y también, si (start_index – i + 1) es impar, multiplique ans por (start_index – i + 1 – 1) /2 + 1 como se indica en el Caso 2.
- Después de recorrer la string S , si la bandera es verdadera y (N – start_index) es impar, multiplique ans por (N – start_index – 1)/2 + 1 .
- Después de completar los pasos anteriores, escriba ans como la respuesta requerida.
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 find the desired number
// of strings
void countStrings(string s, int k)
{
// Store the count of strings
int ans = 1;
// Store the length of the string
int len = s.size();
// Initialize variable to indicate
// the start of the substring
int flag = 0;
// Store the starting index of
// the substring
int start_ind;
// Traverse the string
for (int i = 0; i < len - 1; i++) {
// If sum of adjacent characters
// is K mark the starting index
// and set flag to 1
if (s[i] - '0' + s[i + 1] - '0'
== k
&& flag == 0) {
flag = 1;
start_ind = i;
}
// If sum of adjacent characters
// is not K and the flag variable
// is set, end the substring here
if (flag == 1
&& s[i] - '0'
+ s[i + 1] - '0'
!= k) {
// Set flag to 0 denoting
// the end of substring
flag = 0;
// Check if the length of the
// substring formed is odd
if ((i - start_ind + 1) % 2 != 0)
// Update the answer
ans *= (i - start_ind + 1 - 1)
/ 2
+ 1;
}
}
// If flag is set and end of string
// is reached, mark the end of substring
if (flag == 1
&& (len - start_ind) % 2 != 0)
// Update the answer
ans *= (len - start_ind) / 2 + 1;
// Print the answer
cout << ans;
}
// Driver Code
int main()
{
string S = "313";
int K = 4;
// Function Call
countStrings(S, K);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the desired number
// of strings
static void countStrings(String s, int k)
{
// Store the count of strings
int ans = 1;
// Store the length of the string
int len = s.length();
// Initialize variable to indicate
// the start of the substring
int flag = 0;
// Store the starting index of
// the substring
int start_ind = 0;
// Traverse the string
for(int i = 0; i < len - 1; i++)
{
// If sum of adjacent characters
// is K mark the starting index
// and set flag to 1
if (s.charAt(i) - '0' +
s.charAt(i + 1) - '0' == k && flag == 0)
{
flag = 1;
start_ind = i;
}
// If sum of adjacent characters
// is not K and the flag variable
// is set, end the substring here
if (flag == 1 && s.charAt(i) - '0' +
s.charAt(i + 1) - '0' != k)
{
// Set flag to 0 denoting
// the end of substring
flag = 0;
// Check if the length of the
// substring formed is odd
if ((i - start_ind + 1) % 2 != 0)
// Update the answer
ans *= (i - start_ind + 1 - 1) / 2 + 1;
}
}
// If flag is set and end of string
// is reached, mark the end of substring
if (flag == 1 && (len - start_ind) % 2 != 0)
// Update the answer
ans *= (len - start_ind) / 2 + 1;
// Print the answer
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
String S = "313";
int K = 4;
// Function Call
countStrings(S, K);
}
}
// This code is contributed by jana_sayantan
Python3
# Python program to implement
# the above approach
# Function to find the desired number
# of strings
def countStrings(s, k) :
# Store the count of strings
ans = 1
# Store the length of the string
lenn = len(s)
# Initialize variable to indicate
# the start of the substring
flag = 0
# Traverse the string
for i in range(lenn - 1):
# If sum of adjacent characters
# is K mark the starting index
# and set flag to 1
if (ord(s[i]) - ord('0') + ord(s[i + 1]) - ord('0')
== k
and flag == 0) :
flag = 1
start_ind = i
# If sum of adjacent characters
# is not K and the flag variable
# is set, end the substring here
if (flag == 1
and ord(s[i]) - ord('0')
+ ord(s[i + 1]) - ord('0')
!= k) :
# Set flag to 0 denoting
# the end of substring
flag = 0
# Check if the length of the
# substring formed is odd
if ((i - start_ind + 1) % 2 != 0) :
# Update the answer
ans *= (i - start_ind + 1 - 1) // 2 + 1
# If flag is set and end of string
# is reached, mark the end of substring
if (flag == 1
and (lenn - start_ind) % 2 != 0):
# Update the answer
ans *= (lenn - start_ind) // 2 + 1
# Print the answer
print(ans)
# Driver Code
S = "313"
K = 4
# Function Call
countStrings(S, K)
# This code is contributed by susmitakundugoaldanga
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the desired number
// of strings
static void countStrings(String s, int k)
{
// Store the count of strings
int ans = 1;
// Store the length of the string
int len = s.Length;
// Initialize variable to indicate
// the start of the substring
int flag = 0;
// Store the starting index of
// the substring
int start_ind = 0;
// Traverse the string
for(int i = 0; i < len - 1; i++)
{
// If sum of adjacent characters
// is K mark the starting index
// and set flag to 1
if (s[i] - '0' +
s[i + 1] - '0' == k && flag == 0)
{
flag = 1;
start_ind = i;
}
// If sum of adjacent characters
// is not K and the flag variable
// is set, end the substring here
if (flag == 1 && s[i] - '0' +
s[i + 1] - '0' != k)
{
// Set flag to 0 denoting
// the end of substring
flag = 0;
// Check if the length of the
// substring formed is odd
if ((i - start_ind + 1) % 2 != 0)
// Update the answer
ans *= (i - start_ind + 1 - 1) / 2 + 1;
}
}
// If flag is set and end of string
// is reached, mark the end of substring
if (flag == 1 && (len - start_ind) % 2 != 0)
// Update the answer
ans *= (len - start_ind) / 2 + 1;
// Print the answer
Console.WriteLine(ans);
}
// Driver Code
public static void Main(String[] args)
{
String S = "313";
int K = 4;
// Function Call
countStrings(S, K);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// Function to find the desired number
// of strings
function countStrings(s, k)
{
// Store the count of strings
var ans = 1;
// Store the length of the string
var len = s.length;
// Initialize variable to indicate
// the start of the substring
var flag = 0;
// Store the starting index of
// the substring
var start_ind;
// Traverse the string
for (var i = 0; i < len - 1; i++) {
// If sum of adjacent characters
// is K mark the starting index
// and set flag to 1
if ((s[i].charCodeAt(0) - '0'.charCodeAt(0) +
s[i + 1].charCodeAt(0) - '0'.charCodeAt(0))
== k
&& flag == 0) {
flag = 1;
start_ind = i;
}
// If sum of adjacent characters
// is not K and the flag variable
// is set, end the substring here
if (flag == 1
&& (s[i].charCodeAt(0) - '0'.charCodeAt(0)
+ s[i + 1].charCodeAt(0) -
'0'.charCodeAt(0))
!= k) {
// Set flag to 0 denoting
// the end of substring
flag = 0;
// Check if the length of the
// substring formed is odd
if ((i - start_ind + 1) % 2 != 0)
// Update the answer
ans *= (i - start_ind + 1 - 1)
/ 2
+ 1;
}
}
// If flag is set and end of string
// is reached, mark the end of substring
if (flag == 1
&& (len - start_ind) % 2 != 0)
// Update the answer
ans *= parseInt((len - start_ind) / 2) + 1;
// Print the answer
document.write( ans);
}
// Driver Code
var S = "313";
var K = 4;
// Function Call
countStrings(S, K);
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por single__loop y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA