Dada una string binaria S de longitud N , la tarea es encontrar la longitud de la subsecuencia más larga que sea divisible por 3 . Se permiten ceros iniciales en las subsecuencias.
Ejemplos:
Entrada: S = “1001”
Salida: 4
La subsecuencia más larga divisible por 3 es “1001”.
1001 = 9 que es divisible por 3.
Entrada: S = “1011”
Salida: 3
Enfoque ingenuo: genere todas las subsecuencias posibles y verifique si son divisibles por 3 . La complejidad de tiempo para esto será O((2 N ) * N) .
Enfoque eficiente: la programación dinámica se puede utilizar para resolver este problema. Veamos los estados de DP.
DP[i][r] almacenará la subsecuencia más larga de la substring S[i…N-1] de modo que dé un resto de (3 – r) % 3 cuando se divida por 3 .
Escribamos ahora la relación de recurrencia.
DP[i][r] = max(1 + DP[i + 1][(r * 2 + s[i]) % 3], DP[i + 1][r])
La recurrencia se deriva de las siguientes dos opciones:
- Incluya el índice actual i en la subsecuencia. Por lo tanto, la r se actualizará como r = (r * 2 + s[i]) % 3 .
- No incluya el índice actual en la subsecuencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 100
int dp[N][3];
bool v[N][3];
// Function to return the length of the
// largest sub-string divisible by 3
int findLargestString(string& s, int i, int r)
{
// Base-case
if (i == s.size()) {
if (r == 0)
return 0;
else
return INT_MIN;
}
// If the state has been solved
// before then return its value
if (v[i][r])
return dp[i][r];
// Marking the state as solved
v[i][r] = 1;
// Recurrence relation
dp[i][r]
= max(1 + findLargestString(s, i + 1,
(r * 2 + (s[i] - '0')) % 3),
findLargestString(s, i + 1, r));
return dp[i][r];
}
// Driver code
int main()
{
string s = "101";
cout << findLargestString(s, 0, 0);
return 0;
}
Java
// Java implementation of th approach
class GFG
{
final static int N = 100 ;
final static int INT_MIN = Integer.MIN_VALUE;
static int dp[][] = new int[N][3];
static int v[][] = new int[N][3];
// Function to return the length of the
// largest sub-string divisible by 3
static int findLargestString(String s, int i, int r)
{
// Base-case
if (i == s.length())
{
if (r == 0)
return 0;
else
return INT_MIN;
}
// If the state has been solved
// before then return its value
if (v[i][r] == 1)
return dp[i][r];
// Marking the state as solved
v[i][r] = 1;
// Recurrence relation
dp[i][r] = Math.max(1 + findLargestString(s, i + 1,
(r * 2 + (s.charAt(i) - '0')) % 3),
findLargestString(s, i + 1, r));
return dp[i][r];
}
// Driver code
public static void main (String[] args)
{
String s = "101";
System.out.print(findLargestString(s, 0, 0));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach
import numpy as np
import sys
N = 100
INT_MIN = -(sys.maxsize - 1)
dp = np.zeros((N, 3));
v = np.zeros((N, 3));
# Function to return the length of the
# largest sub-string divisible by 3
def findLargestString(s, i, r) :
# Base-case
if (i == len(s)) :
if (r == 0) :
return 0;
else :
return INT_MIN;
# If the state has been solved
# before then return its value
if (v[i][r]) :
return dp[i][r];
# Marking the state as solved
v[i][r] = 1;
# Recurrence relation
dp[i][r] = max(1 + findLargestString(s, i + 1,
(r * 2 + (ord(s[i]) - ord('0'))) % 3),
findLargestString(s, i + 1, r));
return dp[i][r];
# Driver code
if __name__ == "__main__" :
s = "101";
print(findLargestString(s, 0, 0));
# This code is contributed by AnkitRai01
C#
// C# implementation of th approach
using System;
using System.Collections.Generic;
class GFG
{
readonly static int N = 100 ;
readonly static int INT_MIN = int.MinValue;
static int [,]dp = new int[N, 3];
static int [,]v = new int[N, 3];
// Function to return the length of the
// largest sub-string divisible by 3
static int findLargestString(String s, int i, int r)
{
// Base-case
if (i == s.Length)
{
if (r == 0)
return 0;
else
return INT_MIN;
}
// If the state has been solved
// before then return its value
if (v[i, r] == 1)
return dp[i, r];
// Marking the state as solved
v[i, r] = 1;
// Recurrence relation
dp[i, r] = Math.Max(1 + findLargestString(s, i + 1,
(r * 2 + (s[i] - '0')) % 3),
findLargestString(s, i + 1, r));
return dp[i, r];
}
// Driver code
public static void Main(String[] args)
{
String s = "101";
Console.Write(findLargestString(s, 0, 0));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
var N = 100
var dp = Array.from(Array(N), ()=>Array(3));
var v = Array.from(Array(N), ()=>Array(3));
// Function to return the length of the
// largest sub-string divisible by 3
function findLargestString(s, i, r)
{
// Base-case
if (i == s.length) {
if (r == 0)
return 0;
else
return -1000000000;
}
// If the state has been solved
// before then return its value
if (v[i][r])
return dp[i][r];
// Marking the state as solved
v[i][r] = 1;
// Recurrence relation
dp[i][r]
= Math.max(1 + findLargestString(s, i + 1,
(r * 2 + (s[i].charCodeAt(0) - '0'.charCodeAt(0))) % 3),
findLargestString(s, i + 1, r));
return dp[i][r];
}
// Driver code
var s = "101";
document.write( findLargestString(s, 0, 0));
// This code is contributed by noob2000.
</script>
2
Complejidad de tiempo: O(n)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA