Reverse Prefix of Word

Easy

#1822Time: 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: 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.1 company

Patterns

Two Pointers

Data structures

String Stack

Companies

Optum

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1class Solution {2    public String reversePrefix(String word, char ch) {3        int index = word.indexOf(ch);4        if (index != -1) {5            // Create a StringBuilder from the prefix and reverse it.6            StringBuilder reversedPrefix = new StringBuilder(word.substring(0, index + 1));7            reversedPrefix.reverse();8            9            // Append the rest of the word (suffix).10            reversedPrefix.append(word.substring(index + 1));11            12            // Return the result as a string.13            return reversedPrefix.toString();14        }15        // If ch is not found, return the original word.16        return word;17    }18}

Complexity

Time

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

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.

Trade-offs

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.

This is a more memory and time-efficient approach. Instead of creating multiple substrings, it converts the entire word into a mutable character array. After finding the index of the character ch, it uses a classic two-pointer technique to reverse the prefix part of the array in-place. Finally, a new string is constructed from the modified character array.

Algorithm

Find the index k of the first occurrence of ch.
If ch is not found, return the original word.
Convert the word into a character array chars.
Initialize two pointers, left = 0 and right = k.
While left < right, swap chars[left] and chars[right], then increment left and decrement right.
Create and return a new string from the modified chars array.

Walkthrough

This approach is considered more optimal because it minimizes object creation overhead. By converting the string to a character array at the beginning, all modifications can be done on this single mutable data structure. The two-pointer swap is a standard and efficient algorithm for in-place reversal. left starts at the beginning of the prefix and right starts at the end. They move towards the center, swapping elements at each step, until the entire prefix is reversed. This avoids the cost of creating new string objects for prefixes and suffixes.

1class Solution {2    public String reversePrefix(String word, char ch) {3        int right = word.indexOf(ch);4        5        // If the character is not found, no action is needed.6        if (right == -1) {7            return word;8        }9        10        // Convert string to char array for mutable operations.11        char[] chars = word.toCharArray();12        int left = 0;13        14        // Use two pointers to reverse the prefix in-place.15        while (left < right) {16            char temp = chars[left];17            chars[left] = chars[right];18            chars[right] = temp;19            left++;20            right--;21        }22        23        // Convert the char array back to a string.24        return new String(chars);25    }26}

Complexity

Time

O(N), where N is the length of the `word`. `indexOf` is O(N), `toCharArray()` is O(N), the two-pointer reversal takes O(k) time where k is the prefix length (O(N) in the worst case), and `new String(char[])` is O(N). The total time complexity remains linear.

Space

O(N). A character array of size N is created to store a mutable copy of the string. This is the primary space overhead.

Trade-offs

Pros

More efficient than the string manipulation approach as it avoids creating multiple intermediate string objects. It only creates one character array and one final string.
The in-place reversal on the character array is a common and efficient pattern for such problems.

Cons

The code is slightly more verbose than the one-liner StringBuilder approach, as it requires manual implementation of the two-pointer swap logic.

Solutions

Solution

1class Solution {2public3  String reversePrefix(String word, char ch) {4    int j = word.indexOf(ch);5    if (j == -1) {6      return word;7    }8    char[] cs = word.toCharArray();9    for (int i = 0; i < j; ++i, --j) {10      char t = cs[i];11      cs[i] = cs[j];12      cs[j] = t;13    }14    return String.valueOf(cs);15  }16}

1class Solution {2public:3  string reversePrefix(string word, char ch) {4    int i = word.find(ch);5    if (i != string ::npos) {6      reverse(word.begin(), word.begin() + i + 1);7    }8    return word;9  }10};

1class Solution:2    def reversePrefix(self, word: str, ch: str) -> str: i = word . find(ch) return word if i == - 1 else word[i:: - 1] + word[i + 1:]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem