Supprimer le caractère pour imprimer la plus longue chaîne dans l'ordre alphabétique

Votre logique est incorrecte:

1. Dans if (s.charAt (i) vous comparez le caractère courant de la boucle externe (qui deviendra le premier caractère de la sortie < code> String ) avec le caractère courant de la boucle interne. Cela signifie qu'après avoir ajouté v, w et z à o , vous ajoutez x (depuis v < x ) et récupérez la sortie invalide "vwzx". Vous devez comparer s.charAt (j) au dernier caractère ajouté à o .

2. La résolution du premier problème garantira que la String de sortie est dans l'ordre alphabétique, mais elle ne trouvera pas nécessairement la sortie la plus longue possible. La raison en est que vous ignorez les caractères de l'entrée String uniquement s'ils appartiennent à un préfixe de s (c'est-à-dire tous les caractères d'index o . Cela signifie que pour le "xvwzxz", vous construirez la sortie "vwz", et ne pourrez pas trouver la sortie "vwxz" plus longue, puisque vous n'avez pas de logique pour sauter le premier "z". / p>

Pour cette question, pour être honnête, je n'ai jamais fait la sous-séquence croissante la plus longue auparavant. Je pense que le code des algorithmes efficaces sur cette page Wikipédia - (signalé par Saibot ) semble vraiment bien. Ainsi, j'ai traduit ce code en Java pour vous avec une torsion. Ce code a été modifié pour qu'il fonctionne pour vos cas. Vous pouvez en savoir plus sur cette page Wikipédia pour comprendre les algorithmes.

Au début, je pensais que cette question portait sur l'extraction du caractère d'une chaîne triée sans répétition de caractère.

Comme suspecté que la méthode de Wikipédia est l'une des méthodes les plus efficaces, j'ai soumis le code ci-dessous à un test de référence. J'ai généré 1 000 000 de chaînes, chacune avec le len de 15, et ne contient que des caractères alpha inférieurs. Voici le résultat et notez que le résultat est en millisecondes.

Benchmark: https://ideone.com/4ZBwda

public class Main {
    public static void main(String[] args) {
        System.out.println(wordInSeq("xvwzzzxyxx"));
        System.out.println(wordInSeq("abdb"));
        System.out.println(wordInSeq("xvwzxz"));
    }

    private static String wordInSeq(String s) {

        int P[] = new int[s.length()];
        int M[] = new int[s.length()+1];

        int L = 0;
        for (int i = 0; i < s.length(); i++ )  {
            // Binary search for the largest positive j ≤ L
            // such that X[M[j]] <= X[i]
            int lo = 1;
            int hi = L;

            while ( lo <= hi ){
                // This is equal to round up for / 2
                int mid = ((lo+hi) >> 1) + ((lo + hi) & 1);

                // This was change
                // <  : low to high no repeat
                // <= : low to high repeating
                // >  : high to low no repead
                // >= : high to low repeating 
                if (s.charAt(M[mid]) < s.charAt(i))
                    lo = mid+1;
                else
                    hi = mid-1;
            }
            // After searching, lo is 1 greater than the
            // length of the longest prefix of X[i]
            int newL = lo;

            // The predecessor of X[i] is the last index of 
            // the subsequence of length newL-1
            P[i] = M[newL-1];
            M[newL] = i;

            if (newL > L){
                // If we found a subsequence longer than any we've
                // found yet, update L
                L = newL;
            }
        }

        // Reconstruct the longest increasing subsequence
        char S[] = new char[L];
        int k = M[L];
        for (int i = L - 1; i > -1; i-- ){
            S[i] = s.charAt(k);
            k = P[k];
        }
        return new String(S);
    }
}

Vous avez besoin d'un mécanisme de retour arrière car si la chaîne d'entrée est "abczde", le résultat le plus long est "abcde", pas "abcz".

Voici un exemple d'implémentation:

private static String wordInSeq(String s) {
    StringBuilder buf = new StringBuilder();
    Set<String> words = new HashSet<>();
    wordsInSeq(s, buf, 0, words);
    String longest = "";
    for (String word: words) {
        if (word.length() > longest.length()) {
            longest = word;
        }
    }
    return longest;
}

private static void wordsInSeq(String s, StringBuilder buf, int pos,
        Set<String> words) {
    if (pos >= s.length()) {
        words.add(buf.toString());
    } else {
        int len = buf.length();
        wordsInSeq(s, buf, pos+1, words);
        char cur = s.charAt(pos);
        if (len == 0 || cur > buf.charAt(len-1)) {
            buf.append(s.charAt(pos));
            wordsInSeq(s, buf, pos+1, words);
        }
        buf.setLength(len);
    }
}

Votre logique est incorrecte, comme @Eran l'a expliqué dans sa réponse .

Vous devrait plutôt utiliser la programmation dynamique pour résoudre ce problème, qui est en fait la sous-séquence croissante la plus longue comme indiqué par @SaiBot dans les commentaires.

Donc, pour une chaîne disons xvwzxz , nous initialisons un tableau vide avec des valeurs comme 1 puisque nous pouvons toujours obtenir une séquence de longueur au moins 1.

   private static String wordInSeq(String s) {
        int[][] dp = new int[s.length()][2];
        int max_index = -1;
        for(int i=0;i<s.length();++i){
            dp[i][0] = 1;
            dp[i][1] = i;
            for(int j=i-1;j>=0;--j){
                if(s.charAt(i) > s.charAt(j)){
                    if(dp[i][0] < 1 + dp[j][0]){
                        dp[i][0] = 1 + dp[j][0];
                        dp[i][1] = j;
                    }
                }
            }

            if(max_index == -1 || dp[max_index][0] < dp[i][0]) max_index = i;
        }

        StringBuilder res = new StringBuilder("");
        int temp = max_index;
        while(dp[temp][1] != temp){
            res.append(s.charAt(temp));
            temp = dp[temp][1];
        }
        res.append(s.charAt(temp));
        return res.reverse().toString();
    }

Maintenant, soit i = 0. Nous passons de i à 0 pour chaque caractère et comparons les caractères et obtenons la longueur maximale croissante pour chaque caractère individuel.

i = 0

   x v w z x z
   1 1 2 3 3 4
             ^

i = 1

   x v w z x z
   1 1 2 3 3 1
           ^

i = 2

   x v w z x z
   1 1 2 3 1 1
         ^

Depuis w> v, w + v = 2 (en longueur)

i = 3

   x v w z x z
   1 1 2 1 1 1
       ^

i = 4

   x v w z x z
   1 1 1 1 1 1
     ^

i = 5

   x v w z x z
   1 1 1 1 1 1
   ^

Ainsi, la longueur maximale croissante pour xvwzxz est 4 . Pour construire la réponse à partir de ces entiers, nous pouvons simplement créer un autre tableau (ou un tableau 2D) et conserver un simple index précédent dont nous avons obtenu la réponse maximale et gravir cette échelle pour obtenir la chaîne croissante la plus longue.

Snippet:

x v w z x z
1 1 1 1 1 1

Démo: https://ideone.com/IpIdk7

Remarque importante: Il est fort possible qu'il puisse y avoir plusieurs réponses correctes pour une chaîne donnée. Par exemple, pour efghabcd , efgh et abcd sont des réponses correctes.

Voici la solution:

[vwxy]
[efgh, abcd]

Sortie:

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        System.out.println(longestTextInSeq("xvwzzzxyxx"));
        System.out.println(longestTextInSeq("efghabcd"));
    }

    private static List<String> longestTextInSeq(String s) {
        List<String> list = new ArrayList<String>();
        int visited = 0;
        StringBuilder subs = null;
        while (visited < s.length()) {
            subs = new StringBuilder();
            while (visited < s.length() - 1 && s.charAt(visited) < s.charAt(visited + 1)) {

                // Since we are appending two chars at the same time in every loop, the 2nd
                // char, if not deleted, will be repeated in the next loop
                if (subs.length() > 1) {
                    subs.deleteCharAt(subs.length() - 1);
                }

                subs.append(s.charAt(visited)).append(s.charAt(visited + 1));
                visited++;
            }
            if (subs.length() > 1) {
                list.add(subs.toString());
            }
            visited++;
        }

        // Return the list of longest strings from the list of collected strings
        return longestStrings(list);
    }

    private static List<String> longestStrings(List<String> list) {
        int maxLength = 0;
        List<String> shortList = new ArrayList<String>();
        List<String> longestStrs = new ArrayList<String>();
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(i).charAt(list.get(i).length() - 2) < list.get(j).charAt(0)) {
                    shortList.add(list.get(i).substring(0, list.get(i).length() - 1) + list.get(j));
                }
            }
        }
        if (shortList.size() == 0) {
            shortList = list;
        }
        for (String s : shortList) {
            if (s.length() > maxLength) {
                maxLength = s.length();
            }
        }
        for (String s : shortList) {
            if (s.length() == maxLength) {
                longestStrs.add(s);
            }
        }
        return longestStrs;
    }
}

La logique est simple et compréhensible. J'ai également mis des commentaires importants dans le code. N'hésitez pas à commenter en cas de doute.

[Mise à jour]

La solution mise à jour suivante est basée sur le commentaire de OP:

XXX

Sortie:

[vwz]
[efgh, abcd]