Minimiser la somme finale des indices dans Palindrome

Étant donné une chaîne S de longueur N Sélectionner un Sous-séquence de caractère, supprimez-le et concaténez la partie restante de la chaîne S. Disons que la partie restante sera S1. Ensuite, la tâche consiste à produire le somme minimale possible des indices réels de S1 par rapport à S et S1 doit avoir une longueur supérieure à 1, qui devient un palindrome. S’il n’est pas possible de faire du palindrome S1, alors sortie -1.

Exemples:

Saisir: N = 5, S = “baabx”
Sortir: 5
Explication: Supprimer la sous-séquence aax (baabX), afin que la chaîne restante soit bb, Qui est un palindrome. La somme des indices réels des caractères dans “bb” est 1 + 4 = 5. Parce que les caractères b et b sont placés au 1er et 4ème index de S ou nous pouvons dire la valeur réelle des indices dans une chaîne concaténée par rapport à S. Il convient de noter que, si nous supprimons la sous-séquence bbx(baaboîte) alors la chaîne restante devient “aa”, avec une somme d’indices réels de 2 + 3 = 5. C’est aussi une réponse possible.

Saisir: N = 3, S = “abc”
Sortir: -1
Explication: On peut vérifier que la suppression de toute sous-séquence possible ne peut créer aucune chaîne palindromique, donc aucune somme minimale possible n’existe.

Approche: Mettre en œuvre l’idée ci-dessous pour résoudre le problème

Le problème est Cupide logique basé et peut être résolu en utilisant le HashMap Structure de données. Pour plus de précisions, consultez le Concept d’approche section.

Concept d’approche :

Il est clair que nous devons créer une chaîne palindrome de longueur supérieure à 1, donc la longueur qui est juste supérieure à 1 est 2.

Nous prenons la longueur 2 car elle est juste supérieure à 1 et c’est une longueur telle qu’elle peut former une corde palindrome. Sauf que nous devons minimiser le nombre de caractères dans S1, de sorte que la somme des indices réels soit le minimum possible. Ainsi, 2 est une longueur optimale pour S1.

Ainsi, l’observation vient que nous devons supprimer la sous-séquence de telle sorte que la chaîne de palindrome S1 ne doit avoir que 2 caractères et pour faire du palindrome S1, ces 2 caractères doivent être les mêmes.

Par exemple: S = “bacb”
Sous-séquence supprimée = ac (bcourant alternatifb)
S1 après suppression de la sous-séquence = bb

Veuillez noter que nous pouvons également faire S1 = bab, qui est également un palindrome, à partir du cas ci-dessus. Mais en raison de l’augmentation du nombre de caractères, la somme des indices réels ne fera qu’augmenter davantage. On ne prendra donc pas la longueur 3 pour faire du palindrome S1. Pour minimiser la somme, la valeur réelle des indices de ces deux mêmes caractères doit être la plus proche de premier indice.

Par exemple: S = “baba”

Il peut y avoir deux cas soit supprimer la sous-suite aa(bunbun) ou bb(bunba), ce qui donne S1 comme « bb » ou « aa » respectivement. “bb” a la somme des indices réels comme = 1 + 3 = 4 et “aa” a 2 + 4 = 6 . Comme 4 < 6, Par conséquent, la valeur minimale possible est 4 pour cette affaire. Il convient de noter que les caractères b, b est plus proche du premier indice que a, a dans S.

L’observation finale est:

Trouver deux mêmes caractères dans S, tels qu’ils sont identiques et les plus proches du premier index, Formellement deux mêmes caractères à l’extrême gauche. Exemples:

Des mesures ont été prises pour résoudre le problème :

Créer un booléen drapeau et initialisez-le comme faux.
Créer une variable Somme min.
Créer un HashMap, disons carte.
Exécutez une boucle pour i = 0 à i < N et suivez les étapes ci-dessous dans le cadre de la boucle :
- Si ( map.containsKey( s.charAt( i ) ) == false)
  - map.put(s.charAt( je ), (je + 1))
- Autre
  - minSum = (i + 1) + map.get(s.charAt( i ))
  - flag = true puis casser la boucle.
Si la valeur de l’indicateur est vraie, alors affichez la valeur de Somme min, sinon sortie -1.

Ci-dessous le code pour implémenter l’approche:

Java

// Java code to implement the approach
import java.io.*;
import java.lang.*;
import java.util.*;

class GFG {

    // Driver Function
    public static void main(String[] args)
        throws java.lang.Exception
    {

        int n = 7;
        String s = "bxyzabb";

        // Function call
        minimumSum(s, n);
    }

    // Method for finding minimum possible
    // sum of indices
    static void minimumSum(String s, int n)
    {

        // boolean Flag intialized to false
        boolean flag = false;

        // Variable for holding minimum
        // possible sum of actual indices
        int minSum = 0;

        // HashMap for storing
        // <Character, IndexNumber> pair
        HashMap<Character, Integer> map = new HashMap<>();

        // Loop for traversing over S
        for (int i = 0; i < n; i++) {
            // If current character not
            // exist in Map Then putting
            // that character along with
            // its 1 based indexing
            if (!map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), (i + 1));
            }

            // If current character is
            // already stored in map then
            // initialzing minSum as sum of
            // index of current character
            // and the index stored
            // previously of the same character
            else {
                minSum = (i + 1) + map.get(s.charAt(i));

                // Marking flag as true, So
                // that we can know Palindrome
                // forming is possible or not
                flag = true;
                break;
            }
        }

        // Printing output on
        // the basis of flag
        System.out.println(flag == true ? minSum : -1);
    }
}

Complexité temporelle : O(N), lorsque la chaîne est parcourue
Espace Auxiliaire : O(N), comme HashMap est utilisé