Reverse Only Letters

Definitely the weather is changing in the Twin Cities of Minneapolis and St. Paul. Last night my wife and I slept with a windows in the kitchen opened just a crack. This morning the upstairs temperature was at 69F. During winter we keep the upstairs at 68F. Chances are that this evening will sleep with the windows closed and the heater on.

I need to update my post previous post Count Negative Numbers in a Sorted Matrix. I made an incorrect statement and would like to generate an update. If you are curios, I left the body of the post as it was. I generated an opening note.

I decided to give a try to LeetCode problem 917 Reverse Only Letters. If you are interested, please visit the URI and read the comments and check out the examples.

Given a string S, return the "reversed" string where 
all characters that are not a letter stay in the same place, 
and all letters reverse their positions.

Note:

S.length <= 100
33 <= S[i].ASCIIcode <= 122 
S doesn't contain \ or "

In a nutshell we are given a string and need to reverse it, with a twist. It seems that we should only reverse the position on the letters and no other character. The ASCII characters (https://en.wikipedia.org/wiki/ASCII) between decimal values 33 and 122 map to letters a – z and A – Z which happen to be all letters.

class Solution {
    public String reverseOnlyLetters(String S) {
        
    }
}

In this post we will solve the problem using the Java programming language and the VSCode IDE running on a Windows 10 machine. We need to generate the code for the specified function which takes an input string.

ab-cd
main <<< S ==>ab-cd<== len: 5
main <<<  reverseOnlyLetters ==>dc-ba<==
main <<< reverseOnlyLetters1 ==>dc-ba<==


a-bC-dEf-ghIj
main <<< S ==>a-bC-dEf-ghIj<== len: 13
main <<<  reverseOnlyLetters ==>j-Ih-gfE-dCba<==
main <<< reverseOnlyLetters1 ==>j-Ih-gfE-dCba<==


Test1ng-Leet=code-Q!
main <<< S ==>Test1ng-Leet=code-Q!<== len: 20
main <<<  reverseOnlyLetters ==>Qedo1ct-eeLg=ntse-T!<==
main <<< reverseOnlyLetters1 ==>Qedo1ct-eeLg=ntse-T!<==


a-
main <<< S ==>a-<== len: 2
main <<<  reverseOnlyLetters ==>a-<==
main <<< reverseOnlyLetters1 ==>a-<==


-b
main <<< S ==>-b<== len: 2
main <<<  reverseOnlyLetters ==>-b<==
main <<< reverseOnlyLetters1 ==>-b<==


-a-
main <<< S ==>-a-<== len: 3
main <<<  reverseOnlyLetters ==>-a-<==
main <<< reverseOnlyLetters1 ==>-a-<==

It seems that the test scaffolding that we developed for this problem which is not part of the solution reads and displays the input string and its length. We did that to make sure we test with strings that have odd and even lengths. We then seem to call to implementations of the solution. It seems both generate the same output string.

The first three test cases are the ones provided by LeetCode. The rest I generated to check some conditions.

    /**
     * Test scaffolding
     */
    public static void main(String[] args) {
        
        // **** open scanner ****
        Scanner sc = new Scanner(System.in);

        // **** read string ****
        String S = sc.nextLine();

        // **** close scanner ****
        sc.close();

        // ???? ????
        System.out.println("main <<< S ==>" + S + "<== len: " + S.length());

        // **** reverse and display string ****
        System.out.println("main <<<  reverseOnlyLetters ==>" + reverseOnlyLetters(S) + "<==");

        // **** reverse and display string ****
        System.out.println("main <<< reverseOnlyLetters1 ==>" + reverseOnlyLetters1(S) + "<==");
    }

The test scaffolding reads the input string. It displays the string to visually make sure all is well so far. We then call two different but similar implementations. They both were accepted by LeetCode.

    /**
     * Given a string S, return the "reversed" string where 
     * all characters that are not a letter stay in the same place, 
     * and all letters reverse their positions.
     * Runtime O(n)
     * Runtime: 0 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 37 MB, less than 98.51% of Java online submissions.
     */
    static String reverseOnlyLetters(String S) {

        // **** character array ****
        char[] R = S.toCharArray();

        // **** for ease of use ****
        int len = R.length;
        
        // **** initialize indices ****
        int l = 0;
        int r = len - 1;

        // **** increment 'l' to point to letter (if needed) ****
        for ( ; l < len && !Character.isLetter(R[l]); l++);

        // **** decrement 'r' to point to a letter (if needed) ****
        for ( ; r >= 0 && !Character.isLetter(R[r]); r--);

        // **** loop swapping characters ****
        while (l < r) {

            // **** swap characters ****
            char t = R[l];
            R[l] = R[r];
            R[r] = t;

            // **** increment 'l' to point to a letter (if needed) ****
            l++;
            for ( ; l < len && !Character.isLetter(R[l]); l++);

            // **** decrement 'r' to point to a letter (if needed) ****
            r--;
            for ( ; r >= 0 && !Character.isLetter(R[r]); r--);
        }

        // **** return reversed string ****
        return new String(R);
    }

We start by extracting the characters in the input string into a character array. We do so because a string in Java is an immutable object. It is costly to generate new versions of a string resulting from multiple string manipulations.

We get and save the length of the string to have it handy in future use.

We will traverse the character array in both directions, from left to right and from right to left. We will stop traversing the string when the indices overlap. The reason is that we will swap characters from the front to the back (and obviously from the back to the front).

We initialize the indices and make sure we are pointing to letters and not other characters. We are ready to start looping and moving the indices from the ends to the center of the character array.

We swap the characters, update the indices and make sure we end on letters (not other symbols) in the next pass.

When done, we return the string generated by the character array ‘R’.

    /**
     * Given a string S, return the "reversed" string where 
     * all characters that are not a letter stay in the same place, 
     * and all letters reverse their positions.
     * Runtime: 0 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 37.1 MB, less than 96.62% of Java online submissions.
     * Runtime O(n)
     */
    static String reverseOnlyLetters1(String S) {

        // **** character array ****
        char[] R = S.toCharArray();

        // **** for ease of use ****
        int len = R.length;
        
        // **** initialize indices ****
        int l = 0;
        int r = len - 1;

        // **** loop swapping characters ****
        while (l < r) {

            // **** increment 'l' to point to a letter (if needed) ****
            while (l < r && !Character.isLetter(R[l]))
                l++;

            // **** decrement 'r' to point to a letter (if needed) ****
            while (l < r && !Character.isLetter(R[r]))
                r--;

            // **** swap characters (if needed) ****
            if (l < r) {
                char t = R[l];
                R[l] = R[r];
                R[r] = t;
            }
            
            // **** update indices ****
            l++;
            r--;
        }

        // **** return reversed string ****
        return new String(R);
    }

This is a similar approach. The lines before the loop are like before. Note we do not know yet if the indices are pointing to letters or not.

The condition in the while loop is the same as before.

We first need to point to a letter on each index. Note that in the respective loops, we make sure the indices do not overlap. Now we are ready to swap the characters. The check condition is just to avoid the case when swapping the character with itself. I am not sure it makes sense to check for that. It just adds a condition and makes the code a little more complex. Finally we update the indexes to avoid processing the same set of characters in an infinite loop.

When done we return the string generated by the reversed character array.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address:  john.canessa@gmail.com. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 2834 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.