Reverse String Prefix

Difficulty: Easy | Acceptance: 89.50% | Paid: No Topics: Two Pointers, String

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.

• Examples
• Constraints
• Two Pointers
• String Slicing
• Stack

Examples

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 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, so no operation is performed.

Constraints

1 <= word.length <= 250
word and ch consist of lowercase English letters.

Two Pointers

Intuition Locate the index of the target character. If found, use two pointers starting from the beginning of the string and the found index, swapping characters until they meet in the middle.

Steps

• Find the index of the first occurrence of ch in word.
• If ch is not found, return the original string.
• Convert the string to a mutable array of characters.
• Initialize a left pointer at 0 and a right pointer at the found index.
• While the left pointer is less than the right pointer, swap the characters at these pointers and move them towards the center.
• Convert the array back to a string and return it.

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        try:
            idx = word.index(ch)
        except ValueError:
            return word
        
        res = list(word)
        l, r = 0, idx
        while l < r:
            res[l], res[r] = res[r], res[l]
            l += 1
            r -= 1
        return "".join(res)

Complexity

• Time: O(n), where n is the length of the string. We traverse the string to find the index and then reverse the prefix.
• Space: O(n) to store the character array (or O(1) auxiliary space if modifying in-place like in C++).
• Notes: This is the most standard approach for in-place reversal operations.

String Slicing

Intuition Find the index of the character. If found, split the string into two parts: the prefix (up to and including the character) and the suffix. Reverse the prefix and concatenate it with the suffix.

Steps

• Find the index of ch.
• If not found, return word.
• Extract the prefix substring word[0...idx].
• Extract the suffix substring word[idx+1...].
• Reverse the prefix.
• Return the concatenation of the reversed prefix and the suffix.

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

Complexity

• Time: O(n), as slicing and reversing operations take linear time relative to the string length.
• Space: O(n) to create the new strings.
• Notes: This approach is often more concise in high-level languages but may involve more memory allocations than the two-pointer approach.

Stack

Intuition Iterate through the string, pushing characters onto a stack until the target character is found. Once found, pop characters from the stack to build the reversed prefix, then append the rest of the string.

Steps

• Initialize an empty stack and a result list.
• Iterate through each character in word.
• Push the character onto the stack.
• If the character matches ch, pop all elements from the stack and append them to the result. This reverses the order.
• If ch is never found, return the original string.
• If ch was found, append the remaining characters from word (after the index of ch) to the result.

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        stack = []
        res = []
        found = False
        for c in word:
            stack.append(c)
            if c == ch and not found:
                found = True
                while stack:
                    res.append(stack.pop())
        if not found:
            return word
        return "".join(res)

Complexity

• Time: O(n), as we process each character exactly once.
• Space: O(n), for the stack and the result string.
• Notes: This approach demonstrates the use of a stack for reversal but is generally less efficient than two pointers due to extra memory overhead.