Reverse Prefix of Word

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

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.

Return the resulting string.

• Examples
• Constraints
• Two Pointers
• Stack
• Built-in String Manipulation

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 2. 
Reverse the part of word from 0 to 2 (inclusive), the resulting string is "zxyxxe".

Example 3:

Input: word = "abcd", ch = "z"
Output: "abcd"
Explanation: "z" does not exist in word.

Constraints

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

Two Pointers

Intuition We can find the index of the target character and then use two pointers to swap characters from the start of the string up to that index, effectively reversing the prefix in place.

Steps

• Convert the string to a mutable character array (or list).
• Iterate through the array to find the index of the first occurrence of ch.
• If ch is not found, return the original string.
• Initialize a left pointer at 0 and a right pointer at the found index.
• Swap characters at left and right, then move left forward and right backward until they meet.
• Convert the character array back to a string and return it.

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        chars = list(word)
        index = -1
        for i, c in enumerate(chars):
            if c == ch:
                index = i
                break
        
        if index == -1:
            return word
        
        left, right = 0, index
        while left < right:
            chars[left], chars[right] = chars[right], chars[left]
            left += 1
            right -= 1
            
        return ''.join(chars)

Complexity

• Time: O(n), where n is the length of the string. We traverse the string to find the character and then potentially traverse half of the prefix to reverse it.
• Space: O(n) to store the character array (or O(1) if the language allows in-place string modification like C++).

Stack

Intuition A stack follows Last-In-First-Out (LIFO) order. By pushing characters onto a stack until we find the target character, we can pop them to retrieve the characters in reverse order.

Steps

• Initialize an empty stack and a result list.
• Iterate through the string character by character.
• Push each character onto the stack.
• If the current character matches ch, stop iterating.
• If ch was found, pop all elements from the stack and append them to the result. This reverses the prefix.
• Append the remaining part of the original string (the part after the found index) to the result.
• If ch was not found, simply return the original string.

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        stack = []
        index = -1
        for i, c in enumerate(word):
            stack.append(c)
            if c == ch:
                index = i
                break
        
        if index == -1:
            return word
        
        res = []
        while stack:
            res.append(stack.pop())
        
        res.extend(list(word[index+1:]))
        return ''.join(res)

Complexity

• Time: O(n), where n is the length of the string. We iterate through the prefix once to push and once to pop.
• Space: O(n) to store the stack and the result.

Built-in String Manipulation

Intuition Most programming languages provide built-in methods to find substrings and reverse strings. We can leverage these to solve the problem concisely.

Steps

• Find the index of the first occurrence of ch in word.
• If the index is -1 (not found), return word.
• Extract the substring from the start up to and including the index.
• Reverse this substring.
• Concatenate the reversed substring with the remainder of the original string (from index + 1 to the end).

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        try:
            idx = word.index(ch)
        except ValueError:
            return word
        return word[:idx+1][::-1] + word[idx+1:]

Complexity

• Time: O(n), where n is the length of the string. Finding the index and reversing the substring both take linear time relative to the string length.
• Space: O(n) to create the new string (strings are often immutable in languages like Java, Python, JS).