Reverse Prefix of Word: Beautiful Approaches to LC-2000

Reverse Prefix of Word: The Problem

Reverse Prefix of Word: Given a 0-indexed string word and a character ch, reverse the word segment that starts at index 0 and ends at the index of the first occurrence of ch (inclusive). If the character ch does not exist in word, do nothing.

Reverse Prefix of Word: Constraints

• 1 <= word.length <= 250
• The word consists of lowercase English letters.
• ch is a lowercase English letter.

Reverse Prefix of Word: Examples

• Input: word = “abcdefd”, ch = “d”
• Output: “dcbaefd”

• Input: word = “xyxzxe”, ch = “z”
• Output: “zxyxxe”

• Input: word = “abcd”, ch = “z”
• Output: “abcd”

Reverse Prefix of Word: Pseudocode

// 1 - Receive a WORD and a LETTER
// 2 - Find the INDEX of the first occurence of LETTER in the WORD
// 3 - if the INDEX could not be found at WORD, return the WORD
// 4 - Reverse prefix of WORD, starting from index 0 to INDEX (inclusive)
// 5 - Return the partialy Reversed WORD

String Replacement Strategy

// 1 - Receive a WORD and a LETTER
public String reversePrefix(String word, char ch) {
    int end = 0;
    // 2 - Find the INDEX of the first occurence of LETTER in the WORD
    while(end < word.length() && word.charAt(end) != ch) {
        end++;
    }
    // 3 - if the INDEX could not be found at WORD, return the WORD
    if(end == word.length()) return word;
    // 4 - Reverse prefix of WORD, starting from index 0 to INDEX (inclusive)
    int bgn = 0;
    while(bgn < end) {
        word = word.substring(0, bgn) + word.charAt(end)+
           word.substring(bgn + 1, end)+
           word.charAt(bgn) +
           word.substring(end + 1, word.length());
        end--;
        bgn++;   
    }
    // 5 - Return the partialy Reversed WORD
    return word;
}

Big O Analysis

This strategy solves the problem “Reverse Prefix of Word”, taking 8ms to execute and wasting 42.44 MB of memory. See the numbers below:

Step 2 time complexity is O(n) in the worst case. But Step 4 uses a variation of the “Two Pointers Technique” approach. Instead of a time complexity of O(n), the real complexity is O(n/2). The ultimate time complexity of this algorithm is O(n).

The space complexity is not so good. Strings are immutable. Every time we manipulate the word variable, we will create a copy of the variable in memory.

The Runtime and Memory graphics suggest that it must have a better solution than the one presented.

StringBuilder Replacement Strategy

// 1 - Receive a WORD and a LETTER
public String reversePrefix(String word, char ch) {
    int end = 0;
    // 2 - Find the INDEX of the first occurence of LETTER in the WORD
    while(end < word.length() && word.charAt(end) != ch) {
        end++;
    }
    // 3 - if the INDEX could not be found at WORD, return the WORD
    if(end == word.length()) return word;
    int bgn = 0;
    StringBuilder b = new StringBuilder(word);
    // 4 - Reverse prefix of WORD, starting from index 0 to INDEX (inclusive)
    while(bgn < end) {
        b.replace(bgn, bgn + 1, ""+word.charAt(end)).
        replace(end, end + 1, ""+word.charAt(bgn));
        end--;
        bgn++;   
    }
    // 5 - Return the partialy Reversed WORD
    return b.toString();
}

Big O Analysis

This strategy solves the problem “Reverse Prefix of Word”, taking 1 ms to execute and wasting 41.30 MB of memory. See the numbers below:

The time complexity is still the same, but there was an improvement in the Runtime. The change applied was targeting Memory improvements. In the end, there were Runtime improvements as well. Why? Because the String Replacement Strategy causes an overhead that affects not only the space complexity but also the time complexity.

StringBuilder is mutable and eliminates the String creation overhead. Analysing the changes we can see how String creation impacts the execution time. Nice to see that!

I was missing one final approach. Strings are arrays of chars. What about reversing the word, using a char array approach? That´s what you are going to find out on the next block.

Char Array Replacement Strategy

// 1 - Receive a WORD and a LETTER
public String reversePrefix(String word, char ch) {
    int end = 0;
    char[] letters = word.toCharArray();
    // 2 - Find the INDEX of the first occurence of LETTER in the WORD
    while(end < letters.length && letters[end] != ch) {
        end++;
    }
    // 3 - if the INDEX could not be found at WORD, return the WORD
    if(end == letters.length) return word;
    int bgn = 0;
    // 4 - Reverse prefix of WORD, starting from index 0 to INDEX (inclusive)
    while(bgn < end) {
        char temp = letters[end];
        letters[end] = letters[bgn];
        letters[bgn] = temp;
        end--;
        bgn++;
    }
    // 5 - Return the partialy Reversed WORD
    return new String(letters);
}

Big O Analysis

This strategy solves the problem “Reverse Prefix of Word”, taking 0ms to execute and wasting 41.37 MB of memory. See the numbers below:

The Runtime is amazing: below 0 ms! Removing the object creation saved us a lot of time. On the other hand, there were no Memory improvements. Using StringBuilder seems to be a nice choice if you are targeting Memory improvements. You still use the OO paradigm, manipulating the word as an object. But if you are facing Runtime issues, the array approach is a killer!

Conclusion

You start your coding as simple as possible. Finding an algorithm that solves your problem should be the first goal. When a solution is conceived and proves to work as expected you can start some analysis. Time and space complexity must be your focus.

Strings are immutable and require new copies every time you manipulate them. Every copy will require more memory and more time spent on the String object creation.

StringBuilders are mutable and eliminate the String creation overhead. Analyzing the StringBuilder changes, we can see how String creation impacts the execution time. Removing the temporary strings creation from the solution, the Runtime decreased by 7 ms, and the Memory saved was 1.1 MB.

Arrays are fast! StringBuilder manipulates an array internally to do the magic. But, to mimic a String, you need some overhead. Using a char array directly, you will skip this overhead decreasing Runtime even more (less than 0 ms).

What’s the best choice? It depends on some aspects like your non-functional requirements, the team’s seniority, available time, etc. The main goal of this article is to present you with some approaches to solve the requirements, and pros and cons of each approach. If I made you think if you can find an even better solution, the purpose of this article was achieved!

You can download a version of the code showcased in this article from my GitHub repository.

Check out another article about DSA.

Thank you for reading this article!