# Reverse Prefix of Word
**Difficulty:** EASY
[External](https://leetcode.com/problems/reverse-prefix-of-word)
Canonical: https://scaleengineer.com/dsa/problems/reverse-prefix-of-word
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String, Stack
**Companies:** [Optum](https://scaleengineer.com/companies/optum)
---
## Problem
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
## 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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Two-Pointers on a Character Array
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public String reversePrefix(String word, char ch) {
        int right = word.indexOf(ch);
        
        // If the character is not found, no action is needed.
        if (right == -1) {
            return word;
        }
        
        // Convert string to char array for mutable operations.
        char[] chars = word.toCharArray();
        int left = 0;
        
        // Use two pointers to reverse the prefix in-place.
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
        
        // Convert the char array back to a string.
        return new String(chars);
    }
}
```
### 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.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string reversePrefix(string word, char ch) {
    int i = word.find(ch);
    if (i != string ::npos) {
      reverse(word.begin(), word.begin() + i + 1);
    }
    return word;
  }
};

```

### Python

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

```