Nombre de sous-séquences maximales en utilisant uniquement les caractères dont les indices sont dans GP

Étant donné une chaîne Sla tâche consiste à trouver le nombre de sous-séquences maximales P de S en utilisant uniquement les caractères dont les index sont dans Progression géométrique.
Noter: Considérons l’indexation basée sur 1 dans S.

Exemples :

Saisir: S = “ddee”
Production: 4
Explication:
Si on prend P = « de », alors P apparaît 4 fois dans S. { {1, 3}, {1, 4}, {2, 3}, {2, 4} }

Saisir: S = “geeksforgeeks”
Production: 6
Explication:
Si on prend P = « ek », alors P apparaît 6 fois dans S. { {2, 4}, {3, 4}, {2, 12} {3, 12}, {10, 12}, {11, 12} }

Approche naïve : L’idée est de générer toutes les sous-séquences possibles de la chaîne donnée tels que les index de la chaîne doivent être dans progression géométrique. Maintenant, pour chaque sous-séquence générée, trouvez l’occurrence de chaque sous-séquence et imprimer le maximum parmi ces occurrences.

Complexité temporelle : O(2N)
Espace Auxiliaire : O(1)

Approche efficace : L’idée est d’observer que toute sous-suite P peut être de n’importe quelle longueur. Disons que si P = “abc” et qu’il se produit 10 fois dans S (où “abc” a son index dans GP dans S), alors nous pouvons voir que la sous-séquence “ab” (ayant un index dans GP) se produira également 10 fois dans S. Donc, pour simplifier la solution, la longueur possible de P sera moins qu’égal à 2. Voici les étapes :

  1. Il faut choisir la sous-suite P de longueur supérieur à 1 car P de longueur supérieure à 1 se produira beaucoup plus de temps que de longueur un si S ne contient pas que des caractères uniques.
  2. Pour la longueur 1 compter le fréquence de chaque alphabet dans la chaîne.
  3. Pour la longueur 2, formez un tableau 2D dp[26][26]dp[i][j] indique la fréquence de la chaîne de car(‘a’ + i) + car(‘a’ + j).
  4. La relation de récurrence utilisée à l’étape 2 est donnée par :

dp[i][j] = dp[i][j] + fréquence[i]
où,
fréquence[i] = fréquence du caractère char(‘a’ + i)
dp[i][j] = fréquence de la chaîne formée par current_character + char(‘a’ + i).

  1. La maximum du tableau de fréquences et tableau dp[][] donne le nombre maximal de toute sous-séquence dans la chaîne donnée.

Voici la mise en œuvre de l’approche ci-dessus :

C++

#include <bits/stdc++.h>

using namespace std;

int findMaxTimes(string S)

{

    long long int arr[26];

    long long int dp[26][26];

    

    

    memset(arr, 0, sizeof(arr));

    memset(dp, 0, sizeof(dp));

    

    

    for (int i = 0; i < S.size(); i++) {

        int now = S[i] - 'a';

        for (int j = 0; j < 26; j++) {

            dp[j][now] += arr[j];

        }

        arr[now]++;

    }

    long long int ans = 0;

    

    for (int i = 0; i < 26; i++)

        ans = max(ans, arr[i]);

    

    for (int i = 0; i < 26; i++) {

        for (int j = 0; j < 26; j++) {

            ans = max(ans, dp[i][j]);

        }

    }

    

    return ans;

}

int main()

{

    

    string S = "ddee";

    

    cout << findMaxTimes(S);

    return 0;

}

Java

import java.util.*;

class GFG{

static int findMaxTimes(String S)

{

    int []arr = new int[26];

    int [][]dp = new int[26][26];

    

    

    for(int i = 0; i < S.length(); i++)

    {

        int now = S.charAt(i) - 'a';

        for(int j = 0; j < 26; j++)

        {

            dp[j][now] += arr[j];

        }

        arr[now]++;

    }

    int ans = 0;

    

    for(int i = 0; i < 26; i++)

        ans = Math.max(ans, arr[i]);

    

    for(int i = 0; i < 26; i++)

    {

        for(int j = 0; j < 26; j++)

        {

            ans = Math.max(ans, dp[i][j]);

        }

    }

    

    return ans;

}

public static void main(String[] args)

{

    

    

    String S = "ddee";

    

    System.out.print(findMaxTimes(S));

}

}

Python3

def findMaxTimes(S):

    

    

    arr = [0] * 26

    dp = [[0 for x in range(26)]

             for y in range(26)]

    

    

    for i in range(len(S)):

        now = ord(S[i]) - ord('a')

        

        for j in range(26):

            dp[j][now] += arr[j]

        arr[now] += 1

    ans = 0

    

    for i in range(26):

        ans = max(ans, arr[i])

    

    for i in range(26):

        for j in range(26):

            ans = max(ans, dp[i][j])

    

    return ans

S = "ddee"

print(findMaxTimes(S))

C#

using System;

class GFG{

static int findMaxTimes(String S)

{

    int []arr = new int[26];

    int [,]dp = new int[26, 26];

    

    

    for(int i = 0; i < S.Length; i++)

    {

        int now = S[i] - 'a';

        for(int j = 0; j < 26; j++)

        {

            dp[j, now] += arr[j];

        }

        arr[now]++;

    }

    int ans = 0;

    

    for(int i = 0; i < 26; i++)

        ans = Math.Max(ans, arr[i]);

    

    for(int i = 0; i < 26; i++)

    {

        for(int j = 0; j < 26; j++)

        {

            ans = Math.Max(ans, dp[i, j]);

        }

    }

    

    return ans;

}

public static void Main(String[] args)

{

    

    

    String S = "ddee";

    

    Console.Write(findMaxTimes(S));

}

}

Javascript

<script>

function findMaxTimes(S)

{

    var arr = Array(26).fill(0);

    var dp = Array.from(Array(26), ()=>Array(26).fill(0));

    

    

    for (var i = 0; i < S.length; i++)

    {

        var now = S[i].charCodeAt(0) - 'a'.charCodeAt(0);

        for (var j = 0; j < 26; j++)

        {

            dp[j][now] += arr[j];

        }

        arr[now]++;

    }

    var ans = 0;

    

    for (var i = 0; i < 26; i++)

        ans = Math.max(ans, arr[i]);

    

    for (var i = 0; i < 26; i++)

    {

        for (var j = 0; j < 26; j++)

        {

            ans = Math.max(ans, dp[i][j]);

        }

    }

    

    return ans;

}

var S = "ddee";

document.write( findMaxTimes(S));

</script>

Complexité temporelle : O(max(N*26, 26 * 26))
Espace Auxiliaire : O(26 * 26)

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut