Characters in array are being removed when sorting a string

Question

I am writing a class to print the given string to lexicographical order but in the final method 'reverseOrder()' the array is automatically deleting values from it (I suppose). The method reverseOrder is deleting some characters for selected string such as "dkhc". Thanks

Debugging shows the values are correctly added to the array.

public class LexicalOrder {
    static String biggerIsGreater(String w) {
        String finalString = "";
        char[] charArr = w.toCharArray();
        int largestX = -1;
        // Find the largest x such that P[x]<P[x+1].
        // (If there is no such x, P is the last permutation.)
        for (int i = 0; i < charArr.length - 1; i++) {
            if (charArr[i] < charArr[i + 1]) {
                largestX = i;
            }
        }
        if (largestX == -1) {
            finalString = "no answer";
        }
        int largestY = -1;
        if (largestX != -1) {
            for (int j = 0; j < charArr.length; j++) {
                if (charArr[largestX] < charArr[j]) {
                    largestY = j;
                }
            }
            charArr = swap(charArr, largestX, largestY);
            charArr = reverseOrder(charArr, largestX + 1);
            finalString = new String(charArr);
        }
        return finalString;
    }

    // Method to swap characters in index largestX and largestY
    public static char[] swap(char[] a, int largestX, int largestY) {
        char temp = a[largestY];
        a[largestY] = a[largestX];
        a[largestX] = temp;
        return a;
    }

    // Method to reverse the order of the array from the index
    // largestX + 1 to n (n being last element of array)
    public static char[] reverseOrder(char[] a, int index) {
        int step = 0;
        char[] newArr = new char[a.length];
        for (int j = 0; j < index; j++) {
            System.out.println(j);
            newArr[j] = a[j]; // adding elements to new arr till index=largestX
            System.out.println(newArr[j] = a[j]);
        }
        for (int i = index; i < a.length; i++) {
            System.out.println(i);
            newArr[index] = a[a.length - step - 1]; // adding remaining values but with reversing order
            System.out.println(newArr[index] = a[a.length - step - 1]);
            step++;
        }
        for (char c : newArr)
            System.out.println(c);
        return newArr;
    }

    public static void main(String[] args) {
        System.out.println(biggerIsGreater("dkhc"));
    }
}

What is expected is = hcdk.

But what I get is = hk

I ran the method to check and it clearly adds those elements to the "newArr" array in method 'reverseOrder()' as shown below.

0
h
1
c
2
d
3
k

Output - hk (and two spaces)

The two characters are replaced by two spaces for some reason. P.S : I am following the steps mentioned here link

Note: It works for some words such as "lmno,dcba,etc"

Do you have unit tests with simple use cases where it is not working as expected? — OneCricketeer
– OneCricketeer, Commented Jan 25, 2019 at 23:24
And c is before h in lexicographical ordering, so I'm not sure I understand the expected output — OneCricketeer
– OneCricketeer, Commented Jan 25, 2019 at 23:26
@cricket_007 Sorry but you're not following. The word "dkhc" is my test case and I know the next lexicographical value is "hcdk". But, the array is simply omitting 'c' and 'd' . The same happens with the word "abdc" where the correct output is "acbd" and I get "acd(and a space character) " so here "b" is omitted and is replaced with a " ". But it runs perfectly for "lmno", "dcba", etc. — pacifistprogrammer
– pacifistprogrammer, Commented Jan 25, 2019 at 23:33
It is probably omitted because you are doing something weird with step++; or newArr[index] = a[a.length - step - 1], and just overwriting the index. Why are you trying to print a variable assignment anyway? — OneCricketeer
– OneCricketeer, Commented Jan 25, 2019 at 23:36
@cricket_007 I am printing them just to check whether the values are correctly entered in the array at the right position or not, which by the output I mentioned above, shows that it gets added perfectly. What is strange is that it works for most of the words except a few.Had the logic being wrong, it wouldnt have worked for other words, but it does — pacifistprogrammer
– pacifistprogrammer, Commented Jan 25, 2019 at 23:41

Rmahajan · Accepted Answer · 2019-01-26 00:24:51Z

1

What you have missed is index++. In reverseOrder method increment index++ will give you hcdk expected output.

public static char[] reverseOrder(char[] a, int index) {
        int step = 0;
        char[] newArr = new char[a.length];
        for (int j = 0; j < index; j++) {
            System.out.println(j);
            newArr[j] = a[j]; // adding elements to new arr till index=largestX
            System.out.println(newArr[j] = a[j]);
        }
        for (int i = index; i < a.length; i++) {
            System.out.println(i);
            newArr[index] = a[a.length - step - 1]; // adding remaining values
                                                    // but with reversing order
            System.out.println(newArr[index] = a[a.length - step - 1]);
            step++;index++;
        }
        for (char c : newArr)
            System.out.println(c);
        return newArr;
    }

In your case index value is not getting incremented due to which 2 and 3 item in an array are blank.

answered Jan 26, 2019 at 0:24

Rmahajan

1,3711 gold badge14 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

pacifistprogrammer Over a year ago

You're great! I completely missed that! This line "newArr[index] = a[a.length - step - 1];" was supposed to be "newArr[i] = a[a.length - step - 1];" and you just pointed out the smallest of a mistake. Thank you very much!

Rmahajan Over a year ago

@pacifistprogrammer Welcome :)

Rmahajan Over a year ago

@pacifistprogrammer if this answer helped you, can you upvote it for future reference and visitors

Collectives™ on Stack Overflow

Characters in array are being removed when sorting a string

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related