Problem Description

You are given a string word (0-indexed) and a character ch. Your task is to reverse the portion of the string that starts from index 0 and goes up to and including the first occurrence of character ch.

The key points are:

• Find where character ch first appears in the string
• Reverse the substring from the beginning of the string up to and including that character
• If ch doesn't exist in the string, return the original string unchanged

For example, with word = "abcdefd" and ch = "d":

• The first occurrence of "d" is at index 3
• You need to reverse the substring from index 0 to 3 (inclusive), which is "abcd"
• After reversing, it becomes "dcba"
• The final result is "dcbaefd" (reversed portion + remaining string)

The solution uses the find() method to locate the first occurrence of ch. If ch is not found (returns -1), the original string is returned. Otherwise, it uses Python slicing word[i::-1] to reverse from index i back to the start, then concatenates it with the remaining portion word[i + 1:].

Intuition

The problem asks us to reverse a specific portion of the string - from the beginning up to a certain character. This naturally breaks down into two steps: finding where to stop the reversal, and then performing the reversal itself.

The first insight is that we need to locate the character ch in the string. Python's find() method is perfect for this as it returns the index of the first occurrence, or -1 if not found. This handles both cases mentioned in the problem - when the character exists and when it doesn't.

Once we know where ch is located at index i, we need to reverse everything from index 0 to index i (inclusive). In Python, string slicing with a negative step provides an elegant way to reverse: word[i::-1] starts at index i and goes backwards to the beginning of the string.

The final piece is preserving the rest of the string that comes after the reversed portion. Since we reversed up to index i (inclusive), the remaining untouched part starts from index i + 1. We simply concatenate the reversed portion with word[i + 1:].

The beauty of this approach is its simplicity - we're essentially splitting the string into two parts at the first occurrence of ch, reversing the first part, and then joining them back together. The edge case where ch doesn't exist is naturally handled by returning the original string when find() returns -1.

Learn more about Stack and Two Pointers patterns.

Solution Approach

The implementation follows a straightforward simulation approach with these steps:

1. Find the target character position: Use the find() method to locate the first occurrence of character ch in the string word. This method returns the index of the first match, or -1 if the character is not found.

   i = word.find(ch)

2. Handle the two cases:

   • If i == -1 (character not found), return the original string unchanged
   • If the character is found, proceed with the reversal

3. Perform the reversal using string slicing: When the character is found at index i, we use Python's slicing notation to reverse the prefix:

   word[i::-1]

   This slice starts at index i and steps backwards through the string with step size -1, effectively reversing all characters from index 0 to index i (inclusive).

4. Concatenate with the remaining string: After reversing the prefix, append the rest of the string starting from index i + 1:

   word[i::-1] + word[i + 1:]

The complete solution combines these steps into a single line using a ternary operator:

return word if i == -1 else word[i::-1] + word[i + 1:]

This approach has a time complexity of O(n) where n is the length of the string (for finding the character and creating the new string), and space complexity of O(n) for storing the result string.

Example Walkthrough

Let's walk through the solution with word = "abcdefd" and ch = "d":

Step 1: Find the character

• Call i = word.find("d")
• The first "d" appears at index 3
• So i = 3

Step 2: Check if character exists

• Since i = 3 (not -1), we proceed with reversal

Step 3: Reverse the prefix

• We need to reverse from index 0 to index 3 (inclusive)
• The substring is "abcd"
• Using word[3::-1]:
  • Start at index 3 ('d')
  • Step backwards with -1
  • This gives us: "dcba"

Step 4: Get the remaining string

• Everything after index 3 is word[4:]
• This gives us: "efd"

Step 5: Concatenate the results

• Reversed prefix: "dcba"
• Remaining string: "efd"
• Final result: "dcba" + "efd" = "dcbaefd"

Let's trace through another example where the character doesn't exist: word = "hello" and ch = "x":

Step 1: i = word.find("x") returns -1 Step 2: Since i == -1, we return the original string "hello"

The solution elegantly handles both cases in one line:

return word if i == -1 else word[i::-1] + word[i + 1:]

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string word. This is because:

• The find() method needs to traverse the string to locate the character ch, which takes O(n) time in the worst case
• The string slicing operation word[i::-1] creates a reversed substring from index i to the beginning, which takes O(i+1) time where i ≤ n-1
• The string slicing word[i+1:] takes O(n-i-1) time
• String concatenation takes O(n) time as it needs to create a new string
• Overall, all operations are bounded by O(n)

The space complexity is O(n), where n is the length of the string word. This is because:

• String slicing word[i::-1] creates a new substring of size O(i+1)
• String slicing word[i+1:] creates a new substring of size O(n-i-1)
• The concatenation creates a new string of size n
• Since strings are immutable in Python, these operations create new string objects rather than modifying in place
• The total space used is O(n) for the result string

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Slicing

A common mistake is incorrectly handling the slicing boundaries, particularly confusing whether to include or exclude the character at the found index.

Incorrect approach:

# Wrong: This excludes the character 'ch' from the reversal
return word[index-1::-1] + word[index:]

Why it's wrong: If ch = 'd' is at index 3 in "abcdefd", this would reverse only "abc" (indices 0-2) and concatenate with "defd", resulting in "cbadefd" instead of the correct "dcbaefd".

Correct approach:

# Include the character at 'index' in the reversal
return word[index::-1] + word[index + 1:]

2. Forgetting to Handle the "Not Found" Case

Another pitfall is assuming the character will always exist in the string and not checking for the -1 return value from find().

Incorrect approach:

def reversePrefix(self, word: str, ch: str) -> str:
    index = word.find(ch)
    # Dangerous: No check for index == -1
    return word[index::-1] + word[index + 1:]

Why it's wrong: When ch is not in word, find() returns -1. Using -1 as an index would reverse from the last character backwards, producing incorrect results. For example, with word = "abc" and ch = "z", this would return "cb" instead of "abc".

Correct approach:

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

3. Using index() Instead of find()

Using index() method instead of find() can cause runtime errors.

Incorrect approach:

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

Why it's problematic: While this works, it's less efficient and less clean than using find(). The index() method raises a ValueError when the character is not found, requiring exception handling which adds unnecessary overhead.

Better approach: Use find() which returns -1 for not found cases, allowing for simpler conditional logic without exception handling.