Reverse Prefix of Word

EASY

Description

Given a 0-indexed string word and a character ch, reverse the segment of word 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.

For example, if word = "abcdefd" and ch = "d", then you should reverse the segment that starts at 0 and ends at 3 (inclusive). The resulting string will be "dcbaefd".

Return the resulting string.

Example 1:

Input: word = "abcdefd", ch = "d"
Output: "dcbaefd"
Explanation: The first occurrence of "d" is at index 3. 
Reverse the part of word from 0 to 3 (inclusive), the resulting string is "dcbaefd".

Example 2:

Input: word = "xyxzxe", ch = "z"
Output: "zxyxxe"
Explanation: The first and only occurrence of "z" is at index 3.
Reverse the part of word from 0 to 3 (inclusive), the resulting string is "zxyxxe".

Example 3:

Input: word = "abcd", ch = "z"
Output: "abcd"
Explanation: "z" does not exist in word.
You should not do any reverse operation, the resulting string is "abcd".

Constraints:

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

Approaches

Checkout 2 different approaches to solve Reverse Prefix of Word. Click on different approaches to view the approach and algorithm in detail.

String Manipulation with Substring and StringBuilder

This approach uses built-in Java string methods to solve the problem. It first locates the target character ch. If found, it splits the word into two parts: the prefix (from the start up to and including ch) and the suffix (the rest of the string). The prefix is then reversed using a StringBuilder, and finally, the reversed prefix is concatenated with the suffix to form the result. If ch is not found, the original word is returned unmodified.

Algorithm

Find the index of the first occurrence of ch using word.indexOf(ch).
If ch is not found (index is -1), return the original word.
Extract the prefix word.substring(0, index + 1).
Create a StringBuilder with the prefix and reverse it using reverse().
Append the suffix word.substring(index + 1) to the reversed prefix StringBuilder.
Return the result by converting the StringBuilder to a string.

This method is straightforward because it leverages the power of Java's standard library. The indexOf method provides a quick way to find the boundary for the reversal. Once the boundary index is known, the string is conceptually split. The StringBuilder class is ideal for the reversal part as it is mutable and provides a convenient reverse() method. The final step is simply combining the reversed part with the untouched part of the string.

class Solution {
    public String reversePrefix(String word, char ch) {
        int index = word.indexOf(ch);
        if (index != -1) {
            // Create a StringBuilder from the prefix and reverse it.
            StringBuilder reversedPrefix = new StringBuilder(word.substring(0, index + 1));
            reversedPrefix.reverse();
            
            // Append the rest of the word (suffix).
            reversedPrefix.append(word.substring(index + 1));
            
            // Return the result as a string.
            return reversedPrefix.toString();
        }
        // If ch is not found, return the original word.
        return word;
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the length of the `word`. The `indexOf` method takes O(N), `substring` can take up to O(N), `StringBuilder.reverse()` takes O(k) (where k is the prefix length), and `append` takes O(N-k). The overall complexity is dominated by these linear-time operations.Space Complexity: O(N). Space is required for the `StringBuilder`'s internal character array, potentially for the substrings (depending on JVM implementation), and for the final resulting string. The total space is proportional to the length of the input string.

Pros and Cons

Pros:

Code is concise and highly readable due to the use of high-level APIs like indexOf, substring, and StringBuilder.
The logic is straightforward and easy to follow for those familiar with Java's string manipulation capabilities.

Cons:

Less efficient in terms of memory and speed due to the creation of multiple intermediate string objects (substring calls) and a StringBuilder object. String immutability in Java means each manipulation creates a new object.

Code Solutions

Checking out 3 solutions in different languages for Reverse Prefix of Word. Click on different languages to view the code.

class Solution {
public
  String reversePrefix(String word, char ch) {
    int j = word.indexOf(ch);
    if (j == -1) {
      return word;
    }
    char[] cs = word.toCharArray();
    for (int i = 0; i < j; ++i, --j) {
      char t = cs[i];
      cs[i] = cs[j];
      cs[j] = t;
    }
    return String.valueOf(cs);
  }
}

Video Solution

Watch the video walkthrough for Reverse Prefix of Word

Patterns:

Two Pointers

Data Structures:

StringStack

Companies:

Optum |