Número de subsecuencias de longitud distinta de cero de una string binaria divisible por 3

Dada una string binaria S de longitud N , la tarea es encontrar el número de subsecuencias de longitud distinta de cero que son divisibles por 3 . Se permiten ceros iniciales en las subsecuencias.
Ejemplos: 
 

Entrada: S = “1001” 
Salida: 5 
“11”, “1001”, “0”, “0” y “00” son 
las únicas subsecuencias divisibles por 3.
Entrada: S = “1” 
Salida: 0 
 

Enfoque ingenuo: genere todas las subsecuencias posibles y verifique si son divisibles por 3. La complejidad del tiempo para esto será O ((2 ^N ) * N).
Mejor enfoque: la programación dinámica se puede utilizar para resolver este problema. Veamos los estados del DP. 
DP[i][r] almacenará el número de subsecuencias de la substring S[i…N-1] de modo que den un resto de (3 – r) % 3 cuando se divide por 3 . 
Escribamos ahora la relación de recurrencia. 
 

DP[i][r] = DP[i + 1][(r * 2 + s[i]) % 3] + DP[i + 1][r] 
 

La recurrencia se deriva de las dos opciones siguientes: 
 

1. Incluya el índice actual i en la subsecuencia. Por lo tanto, la r se actualizará como r = (r * 2 + s[i]) % 3 .
2. No incluya un índice actual en la subsecuencia.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of th approach
#include <bits/stdc++.h>
using namespace std;
#define N 100
 
int dp[N][3];
bool v[N][3];
 
// Function to return the number of
// sub-sequences divisible by 3
int findCnt(string& s, int i, int r)
{
    // Base-cases
    if (i == s.size()) {
        if (r == 0)
            return 1;
        else
            return 0;
    }
 
    // 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]
        = findCnt(s, i + 1, (r * 2 + (s[i] - '0')) % 3)
          + findCnt(s, i + 1, r);
 
    return dp[i][r];
}
 
// Driver code
int main()
{
    string s = "11";
 
    cout << (findCnt(s, 0, 0) - 1);
 
    return 0;
}

// Java implementation of th approach
class GFG
{
 
    static final int N = 100;
     
    static int dp[][] = new int[N][3];
    static int v[][] = new int[N][3];
     
    // Function to return the number of
    // sub-sequences divisible by 3
    static int findCnt(String s, int i, int r)
    {
        // Base-cases
        if (i == s.length())
        {
            if (r == 0)
                return 1;
            else
                return 0;
        }
     
        // 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] = findCnt(s, i + 1, (r * 2 + (s.charAt(i) - '0')) % 3)
                    + findCnt(s, i + 1, r);
     
        return dp[i][r];
    }
     
    // Driver code
    public static void main (String[] args)
    {
        String s = "11";
     
        System.out.print(findCnt(s, 0, 0) - 1);
     
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of th approach
import numpy as np
N = 100
 
dp = np.zeros((N, 3));
v = np.zeros((N, 3));
 
# Function to return the number of
# sub-sequences divisible by 3
def findCnt(s, i, r) :
 
    # Base-cases
    if (i == len(s)) :
         
        if (r == 0) :
            return 1;
        else :
            return 0;
 
    # 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] = findCnt(s, i + 1, (r * 2 +
                      (ord(s[i]) - ord('0'))) % 3) + \
               findCnt(s, i + 1, r);
 
    return dp[i][r];
 
# Driver code
if __name__ == "__main__" :
 
    s = "11";
 
    print(findCnt(s, 0, 0) - 1);
 
# This code is contributed by AnkitRai01

// C# implementation of th approach
using System;
 
class GFG
{
 
    static readonly int N = 100;
     
    static int [,]dp = new int[N, 3];
    static int [,]v = new int[N, 3];
     
    // Function to return the number of
    // sub-sequences divisible by 3
    static int findCnt(String s, int i, int r)
    {
        // Base-cases
        if (i == s.Length)
        {
            if (r == 0)
                return 1;
            else
                return 0;
        }
     
        // 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] = findCnt(s, i + 1, (r * 2 + (s[i] - '0')) % 3)
                    + findCnt(s, i + 1, r);
     
        return dp[i, r];
    }
     
    // Driver code
    public static void Main(String[] args)
    {
        String s = "11";
     
        Console.Write(findCnt(s, 0, 0) - 1);
     
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of th approach
var N = 100
 
var dp = Array.from(Array(N), ()=> Array(3));
var v = Array.from(Array(N), ()=> Array(3));
 
// Function to return the number of
// sub-sequences divisible by 3
function findCnt(s, i, r)
{
    // Base-cases
    if (i == s.length) {
        if (r == 0)
            return 1;
        else
            return 0;
    }
 
    // 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]
        = findCnt(s, i + 1, (r * 2 + (s[i] - '0')) % 3)
          + findCnt(s, i + 1, r);
 
    return dp[i][r];
}
 
// Driver code
var s = "11";
document.write( (findCnt(s, 0, 0) - 1));
 
</script>

1

Complejidad de tiempo: O(n)