Dada una string que contiene solo dos caracteres, es decir, R y K (como RRKRRKKKKKK). La tarea es encontrar el valor máximo de N para una subsecuencia posible de la forma R—N veces y luego K—N veces (es decir, de la forma R^NK^N).
Nota: La string de k debe comenzar después de la string de R, es decir, la primera k que se consideraría para la string ‘K’ debe ocurrir después de la última R de la string ‘R’ en la string dada. Además, la longitud de la subsecuencia resultante será 2*N.
Ejemplos :
Entrada : RRRKRRKKRRKKK
Salida : 5
Si tomamos R en los índices 0, 1, 2, 4, 5 y K en los índices 6, 7, 10, 11, 12
, obtenemos una subsecuencia máxima de la forma R^NK^N, donde N = 5.
Entrada : KKKKRRRRK
Salida : 1
Si tomamos R en el índice 4 (o 5 o 6 o 7) y K en el índice 8
, obtenemos la subsecuencia deseada con N = 1.
Acercarse:
- Calcula el número de R antes de una K.
- Calcula el número de K después de una K, incluida esa K.
- Guárdelos en una tabla con una cantidad de R en la tabla [x] [0] y una cantidad de K en la tabla [x] [1].
- El mínimo de los dos da el valor de n para cada K y devolveremos el máximo n.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the maximum
// length of a substring of form R^nK^n
#include<bits/stdc++.h>
using namespace std;
// function to calculate the maximum
// length of substring of the form R^nK^n
int find(string s)
{
int max = 0, i, j = 0, countk = 0, countr = 0;
int table[s.length()][2];
// Count no. Of R's before a K
for (i = 0; i < s.length(); i++) {
if (s[i] == 'R')
countr++;
else
table[j++][0] = countr;
}
j--;
// Count no. Of K's after a K
for (i = s.length() - 1; i >= 0; i--) {
if (s[i] == 'K') {
countk++;
table[j--][1] = countk;
}
// Update maximum length
if (min(table[j + 1][0], table[j + 1][1]) > max)
max = min(table[j + 1][0], table[j + 1][1]);
}
return max;
}
// Driver code
int main()
{
string s = "RKRRRKKRRKKKKRR";
int n = find(s);
cout<<(n);
}
// This code is contributed by
// Surendra_Gangwar
Java
// Java program to find the maximum
// length of a substring of form R^nK^n
public class gfg {
// function to calculate the maximum
// length of substring of the form R^nK^n
int find(String s)
{
int max = 0, i, j = 0, countk = 0, countr = 0;
int table[][] = new int[s.length()][2];
// Count no. Of R's before a K
for (i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'R')
countr++;
else
table[j++][0] = countr;
}
j--;
// Count no. Of K's after a K
for (i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == 'K') {
countk++;
table[j--][1] = countk;
}
// Update maximum length
if (Math.min(table[j + 1][0], table[j + 1][1]) > max)
max = Math.min(table[j + 1][0], table[j + 1][1]);
}
return max;
}
// Driver code
public static void main(String srgs[])
{
String s = "RKRRRKKRRKKKKRR";
gfg ob = new gfg();
int n = ob.find(s);
System.out.println(n);
}
}
Python3
# Python3 program to find the maximum # length of a substring of form R^nK^n # Function to calculate the maximum # length of substring of the form R^nK^n def find(s): Max = j = countk = countr = 0 table = [[0, 0] for i in range(len(s))] # Count no. Of R's before a K for i in range(0, len(s)): if s[i] == 'R': countr += 1 else: table[j][0] = countr j += 1 j -= 1 # Count no. Of K's after a K for i in range(len(s) - 1, -1, -1): if s[i] == 'K': countk += 1 table[j][1] = countk j -= 1 # Update maximum length if min(table[j + 1][0], table[j + 1][1]) > Max: Max = min(table[j + 1][0], table[j + 1][1]) return Max # Driver code if __name__ == "__main__": s = "RKRRRKKRRKKKKRR" print(find(s)) # This code is contributed by Rituraj Jain
C#
// C# program to find the maximum
// length of a substring of
// form R^nK^n
using System;
class GFG
{
// function to calculate the
// maximum length of substring
// of the form R^nK^n
static int find(String s)
{
int max = 0, i, j = 0,
countk = 0, countr = 0;
int [,]table= new int[s.Length, 2];
// Count no. Of R's before a K
for (i = 0; i < s.Length; i++)
{
if (s[i] == 'R')
countr++;
else
table[(j++),0] = countr;
}
j--;
// Count no. Of K's after a K
for (i = s.Length - 1; i >= 0; i--)
{
if (s[i] == 'K')
{
countk++;
table[j--, 1] = countk;
}
// Update maximum length
if (Math.Min(table[j + 1, 0],
table[j + 1, 1]) > max)
max = Math.Min(table[j + 1, 0],
table[j + 1, 1]);
}
return max;
}
// Driver code
static public void Main(String []srgs)
{
String s = "RKRRRKKRRKKKKRR";
int n = find(s);
Console.WriteLine(n);
}
}
// This code is contributed
// by Arnab Kundu
Javascript
<script>
// JavaScript program to find the maximum
// length of a substring of form R^nK^n
// function to calculate the maximum
// length of substring of the form R^nK^n
function find(s)
{
let max = 0, i, j = 0, countk = 0, countr = 0;
let table = new Array(s.length);
for(let i=0;i<s.length;i++)
{
table[i]=new Array(2);
}
// Count no. Of R's before a K
for (i = 0; i < s.length; i++) {
if (s[i] == 'R')
countr++;
else
table[j++][0] = countr;
}
j--;
// Count no. Of K's after a K
for (i = s.length - 1; i >= 0; i--) {
if (s[i] == 'K') {
countk++;
table[j--][1] = countk;
}
// Update maximum length
if (Math.min(table[j + 1][0], table[j + 1][1]) > max)
max = Math.min(table[j + 1][0], table[j + 1][1]);
}
return max;
}
// Driver code
let s = "RKRRRKKRRKKKKRR";
let n=find(s);
document.write(n);
// This code is contributed by avanitrachhadiya2155
</script>
4
Complejidad de tiempo: O(n) donde ln es la longitud de la substring.
Publicación traducida automáticamente
Artículo escrito por urvashijuhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA