Remove char to print the longest string in alphabetical order

Question

I am looking for a solution to print the longest string in alphabetic order from an input string.

Limitation: we have to take care of the char positions.

Example 1: input: abdb, output: abd, Explanation: abd is the longest string from the input string, if I remove b.

Example 2: input: xvwzxz, output: vwxz, Explanation: if I remove xz I will get the longest string. I have to remove 1st and 4th char.

MyCode:

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

    private static String wordInSeq(String s) {
        
        int max=0; String maxl = "";
        System.out.println(s.length());
        for(int i=0; i<s.length()-1;i++){
            String o = Character.toString(s.charAt(i));
            for(int j=i+1; j<s.length()-1;j++){
                if(s.charAt(i)<s.charAt(j)){
                    if(!o.contains(Character.toString(s.charAt(j))))
                    o=o+Character.toString(s.charAt(j));
                }
                        
            }
            if(max < o.length()){
                max = o.length();
                maxl = o;
            }
            //System.out.println(maxl);
        }
        return maxl;
    }
}

above code is passing only a few scenarios as output is not coming in alphabetic order.

If I pass xvwzxz, the output is: vwzx. It's taking Z at 4th position whereas it should take Z at the last position.

We have to get the exact solution.

Thank you in advance!

Answer 1

For this questions, to be honest, I have not done the Longest increasing subsequence before. I think the Efficient algorithms code at this Wikipedia page -(Pointed out by Saibot) look really good. Thus, I translated that code into Java for you with a twist. That code was modified so that it will work for your cases. You can read more on that Wikipedia page to understand the algorithms.

At first, I thought this question was about getting the character out from a string sorted without repeating character.

As suspected that Wikipedia's method is one of the most efficient methods, I put the code below through a benchmark test. I generated 1,000,000 strings, each with the len of 15, and only contain lower-alpha characters. Below is the result and take note that the result is in milliseconds.

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);
    }
}

Answer 2

Your logic is incorrect as @Eran explained in his answer.

You should instead use dynamic programming to solve this, which is actually Longest increasing subsequence as pointed by @SaiBot in the comments.

So, for a string say xvwzxz, we initialize an empty array with values as 1 since we can always get a sequence of length at least 1.

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

Now, let i=0. We move from i till 0 for every character and compare characters and get the maximum increasing length for each individual character.

i=0

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

i=1

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

i=2

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

Since w > v, w + v = 2(in length)

i=3

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

i=4

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

i=5

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

So, the maximum increasing length for xvwzxz is 4. To construct the answer from these integers, we can just create another array(or a 2D array) and keep a simple previous index from whom we got the maximum answer and climb up that ladder to get the actual longest increasing string .

Snippet:

   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();
    }

Demo: https://ideone.com/IpIdk7

Important Note: It is quite possible that there can be multiple correct answers for a given string. For example, for efghabcd, both efgh and abcd are correct answers.

Answer 3

You need a backtracking mechanism because if the input string is "abczde", the longest result is "abcde", not "abcz".

Here is an example of implementation:

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);
    }
}

Answer 4

Your logic is incorrect:

1. In if (s.charAt(i)<s.charAt(j)) you compare the current character of the outer loop (which will become the first character of the output String) with the current character of the inner loop. This means that after adding v, w and z to o, you add x (since v < x) and get the invalid output "vwzx". You should compare s.charAt(j) to the last character added to o.

2. Fixing the first issue will make sure the output String is in alphabetic order, but it won't necessarily find the longest possible output. The reason is that you only skip characters of the input String if they belong to a prefix of s (i.e. all the characters with index < i) or if you already added them to o. This means that for the "xvwzxz", you'll build the "vwz" output, and won't be able to find the longer "vwxz" output, since you don't have logic to skip the first 'z'.