Dada una string str , la tarea es encontrar la longitud máxima K tal que existan dos subsecuencias A y B cada una de longitud K tales que A = B y el número de índices comunes entre A y B es como máximo K – 1 .
Ejemplos:
Entrada: str = “geeksforgeeks”
Salida: 12
Las dos subsecuencias son
str[0…1] + str[3…12] = “geksforgeeks”
y str[0] + str[2…12] = “geksforgeeks”.
Entrada: str = “abcddefg”
Salida: 7
Enfoque: encuentre cualquier par de la misma letra con un número mínimo de letras entre ellas, digamos que este número mínimo sea X , ahora la respuesta del problema es len (str) – (X + 1) . Se agrega uno en X para no contar una letra del par.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 26;
// Function to return the required
// length of the subsequences
int maxLength(string str, int len)
{
// To store the result
int res = 0;
// To store the last visited
// position of lowercase letters
int lastPos[MAX];
// Initialisation of frequency array to -1 to
// indicate no character has previously occured
for (int i = 0; i < MAX; i++) {
lastPos[i] = -1;
}
// For every character of the string
for (int i = 0; i < len; i++) {
// Get the index of the current character
int C = str[i] - 'a';
// If the current character has
// appeared before in the string
if (lastPos[C] != -1) {
// Update the result
res = max(len - (i - lastPos[C] - 1) - 1, res);
}
// Update the last position
// of the current character
lastPos[C] = i;
}
return res;
}
// Driver code
int main()
{
string str = "geeksforgeeks";
int len = str.length();
cout << maxLength(str, len);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int MAX = 26;
// Function to return the required
// length of the subsequences
static int maxLength(String str, int len)
{
// To store the result
int res = 0;
// To store the last visited
// position of lowercase letters
int lastPos[] = new int[MAX];
// Initialisation of frequency array to -1 to
// indicate no character has previously occured
for (int i = 0; i < MAX; i++)
{
lastPos[i] = -1;
}
// For every character of the String
for (int i = 0; i < len; i++)
{
// Get the index of the current character
int C = str.charAt(i) - 'a';
// If the current character has
// appeared before in the String
if (lastPos[C] != -1)
{
// Update the result
res = Math.max(len - (i -
lastPos[C] - 1) - 1, res);
}
// Update the last position
// of the current character
lastPos[C] = i;
}
return res;
}
// Driver code
public static void main(String args[])
{
String str = "geeksforgeeks";
int len = str.length();
System.out.println(maxLength(str, len));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python implementation of the approach
MAX = 26;
# Function to return the required
# length of the subsequences
def maxLength(str, len):
# To store the result
res = 0;
# To store the last visited
# position of lowercase letters
lastPos = [0] * MAX;
# Initialisation of frequency array to -1 to
# indicate no character has previously occured
for i in range(MAX):
lastPos[i] = -1;
# For every character of the String
for i in range(len):
# Get the index of the current character
C = ord(str[i]) - ord('a');
# If the current character has
# appeared before in the String
if (lastPos[C] != -1):
# Update the result
res = max(len - (i - lastPos[C] - 1) - 1, res);
# Update the last position
# of the current character
lastPos[C] = i;
return res;
# Driver code
if __name__ == '__main__':
str = "geeksforgeeks";
len = len(str);
print(maxLength(str, len));
# This code is contributed by 29AjayKumar
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 26;
// Function to return the required
// length of the subsequences
static int maxLength(string str, int len)
{
// To store the result
int res = 0;
// To store the last visited
// position of lowercase letters
int []lastPos = new int[MAX];
// Initialisation of frequency array to -1 to
// indicate no character has previously occured
for (int i = 0; i < MAX; i++)
{
lastPos[i] = -1;
}
// For every character of the String
for (int i = 0; i < len; i++)
{
// Get the index of the current character
int C = str[i] - 'a';
// If the current character has
// appeared before in the String
if (lastPos[C] != -1)
{
// Update the result
res = Math.Max(len - (i -
lastPos[C] - 1) - 1, res);
}
// Update the last position
// of the current character
lastPos[C] = i;
}
return res;
}
// Driver code
public static void Main()
{
string str = "geeksforgeeks";
int len = str.Length;
Console.WriteLine(maxLength(str, len));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
var MAX = 26;
// Function to return the required
// length of the subsequences
function maxLength(str, len)
{
// To store the result
var res = 0;
// To store the last visited
// position of lowercase letters
var lastPos = Array(MAX);
// Initialisation of frequency array to -1 to
// indicate no character has previously occured
for (var i = 0; i < MAX; i++) {
lastPos[i] = -1;
}
// For every character of the string
for (var i = 0; i < len; i++) {
// Get the index of the current character
var C = str[i].charCodeAt(0) - 'a'.charCodeAt(0);
// If the current character has
// appeared before in the string
if (lastPos[C] != -1) {
// Update the result
res = Math.max(len - (i - lastPos[C] - 1) - 1, res);
}
// Update the last position
// of the current character
lastPos[C] = i;
}
return res;
}
// Driver code
var str = "geeksforgeeks";
var len = str.length;
document.write( maxLength(str, len));
</script>
Producción:
12
Complejidad de tiempo: O(n) donde n es la longitud de la string de entrada.
Publicación traducida automáticamente
Artículo escrito por durgeshkumar30508 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA