Dada una string numérica s que consta de dígitos del 0 al 9, la tarea es encontrar la longitud de la subsecuencia más grande que consta de un par de dígitos alternos.
Una subsecuencia de dígitos alternos que consta de dos dígitos diferentes a y b se puede representar como «abababababababababab…». .
Ejemplos:
Entrada: s = “1542745249842”
Salida: 6
Explicación:
La substring más grande de dígitos alternos en la string dada es 424242.Entrada: s = “1212312323232”
Salida: 9
Explicación:
La substring más grande de dígitos alternos en la string dada es 232323232.
Enfoque: La string consta únicamente de dígitos decimales, es decir, 0-9, por lo que se puede verificar la secuencia para detectar la presencia de todas las subsecuencias posibles que constan de dos dígitos alternos. Para este propósito, siga el siguiente enfoque:
- Use bucles anidados de 0 a 9 cada uno, para seleccionar el par de dígitos ordenados. Cuando los dígitos son iguales , la string no se recorre. Cuando los dígitos son diferentes, entonces se recorre la string y se encuentra la longitud de la subsecuencia que consiste en los dígitos del par ordenado que ocurren como dígitos alternos.
- Si la longitud máxima es 1 , implica que el segundo dígito en cualquiera de los pares ordenados nunca ocurrió en la secuencia dada, lo que la convierte en una secuencia de un solo dígito. El tipo requerido de subsecuencia en tal secuencia no existiría, por lo tanto, generaría 0.
- Si la longitud máxima encontrada es mayor que 1 , esto significa que hay al menos 2 dígitos diferentes presentes en la secuencia dada, por lo que se genera esta longitud encontrada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to find the length of the
// largest subsequence consisting of
// a pair of alternating digits
void largestSubsequence(string s)
{
// Variable initialization
int maxi = 0;
char prev1;
// Nested loops for iteration
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
// Check if i is not equal to j
if (i != j) {
// Initialize length as 0
int len = 0;
prev1 = j + '0';
// Iterate from 0 till the
// size of the string
for (int k = 0; k < s.size(); k++) {
if (s[k] == i + '0'
&& prev1 == j + '0') {
prev1 = s[k];
// Increment length
len++;
}
else if (s[k] == j + '0'
&& prev1 == i + '0') {
prev1 = s[k];
// Increment length
len++;
}
}
// Update maxi
maxi = max(len, maxi);
}
}
}
// Check if maxi is not equal to
// 1 the print it otherwise print 0
if (maxi != 1)
cout << maxi << endl;
else
cout << 0 << endl;
}
// Driver Code
int main()
{
// Given string
string s = "1542745249842";
// Function call
largestSubsequence(s);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the length of the
// largest subsequence consisting of
// a pair of alternating digits
static void largestSubsequence(char []s)
{
// Variable initialization
int maxi = 0;
char prev1;
// Nested loops for iteration
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
// Check if i is not equal to j
if (i != j)
{
// Initialize length as 0
int len = 0;
prev1 = (char) (j + '0');
// Iterate from 0 till the
// size of the String
for (int k = 0; k < s.length; k++)
{
if (s[k] == i + '0' &&
prev1 == j + '0')
{
prev1 = s[k];
// Increment length
len++;
}
else if (s[k] == j + '0' &&
prev1 == i + '0')
{
prev1 = s[k];
// Increment length
len++;
}
}
// Update maxi
maxi = Math.max(len, maxi);
}
}
}
// Check if maxi is not equal to
// 1 the print it otherwise print 0
if (maxi != 1)
System.out.print(maxi + "\n");
else
System.out.print(0 + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Given String
String s = "1542745249842";
// Function call
largestSubsequence(s.toCharArray());
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program for the above approach
# Function to find the length of the
# largest subsequence consisting of
# a pair of alternating digits
def largestSubsequence(s):
# Variable initialization
maxi = 0
# Nested loops for iteration
for i in range(10):
for j in range(10):
# Check if i is not equal to j
if (i != j):
# Initialize length as 0
lenn = 0
prev1 = chr(j + ord('0'))
# Iterate from 0 till the
# size of the string
for k in range(len(s)):
if (s[k] == chr(i + ord('0')) and
prev1 == chr(j + ord('0'))):
prev1 = s[k]
# Increment length
lenn += 1
elif (s[k] == chr(j + ord('0')) and
prev1 == chr(i + ord('0'))):
prev1 = s[k]
# Increment length
lenn += 1
# Update maxi
maxi = max(lenn, maxi)
# Check if maxi is not equal to
# 1 the print otherwise pr0
if (maxi != 1):
print(maxi)
else:
print(0)
# Driver Code
if __name__ == '__main__':
# Given string
s = "1542745249842"
# Function call
largestSubsequence(s)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the length of the
// largest subsequence consisting of
// a pair of alternating digits
static void largestSubsequence(char []s)
{
// Variable initialization
int maxi = 0;
char prev1;
// Nested loops for iteration
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
// Check if i is not equal to j
if (i != j)
{
// Initialize length as 0
int len = 0;
prev1 = (char) (j + '0');
// Iterate from 0 till the
// size of the String
for (int k = 0; k < s.Length; k++)
{
if (s[k] == i + '0' &&
prev1 == j + '0')
{
prev1 = s[k];
// Increment length
len++;
}
else if (s[k] == j + '0' &&
prev1 == i + '0')
{
prev1 = s[k];
// Increment length
len++;
}
}
// Update maxi
maxi = Math.Max(len, maxi);
}
}
}
// Check if maxi is not equal to
// 1 the print it otherwise print 0
if (maxi != 1)
Console.Write(maxi + "\n");
else
Console.Write(0 + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given String
String s = "1542745249842";
// Function call
largestSubsequence(s.ToCharArray());
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// Js program for the above approach
// Function to find the length of the
// largest subsequence consisting of
// a pair of alternating digits
function largestSubsequence(s)
{
// Variable initialization
let maxi = 0;
let prev1;
// Nested loops for iteration
for (let i = 0; i < 10; i++) {
for (let j = 0; j < 10; j++) {
// Check if i is not equal to j
if (i != j) {
// Initialize length as 0
let len = 0;
prev1 = String(j) ;
// Iterate from 0 till the
// size of the string
for (let k = 0; k < s.length; k++) {
if (s[k] == String(i )
&& prev1 == String(j)) {
prev1 = s[k];
// Increment length
len++;
}
else if (s[k] == String(j)
&& prev1 == String(i)) {
prev1 = s[k];
// Increment length
len++;
}
}
// Update maxi
maxi = Math.max(len, maxi);
}
}
}
// Check if maxi is not equal to
// 1 the print it otherwise print 0
if (maxi != 1)
document.write( maxi ,'<br>');
else
document.write( 0 ,'<br>');
}
// Driver Code
// Given string
let s = "1542745249842";
// Function call
largestSubsequence(s);
// This code is contributed by rohitsingh07052.
</script>
Producción:
6
Complejidad de Tiempo: O(10*10*N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por costheta_z y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA