Reverse Prefix of Word

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".

def reverse_prefix(word: str, ch: str) -> str:
    """Reverses the prefix of a string until the first occurrence of a character.

    Args:
        word: The input string.
        ch: The character to find.

    Returns:
        The modified string with the reversed prefix.
    """
    try:
        index = word.index(ch)
        prefix = word[:index+1]
        reversed_prefix = prefix[::-1]
        return reversed_prefix + word[index+1:]
    except ValueError:
        return word


# Example Usage
word1 = "abcdefd"
ch1 = "d"
print(f"Input: word = '{word1}', ch = '{ch1}'")
print(f"Output: {reverse_prefix(word1, ch1)}")  # Output: dcbaefd

word2 = "xyxzxe"
ch2 = "z"
print(f"Input: word = '{word2}', ch = '{ch2}'")
print(f"Output: {reverse_prefix(word2, ch2)}")  # Output: zxyxxe

word3 = "abcd"
ch3 = "z"
print(f"Input: word = '{word3}', ch = '{ch3}'")
print(f"Output: {reverse_prefix(word3, ch3)}")  # Output: abcd

Naive Solution

The provided solution is already quite efficient, addressing the problem directly without unnecessary overhead. A more 'naive' approach might involve manually iterating through the string to find the character, and then constructing a new string by concatenating reversed and non-reversed parts. However, Python's built-in string functions and slicing capabilities make the given solution optimal for readability and performance.

Optimal Solution

The presented solution can be considered optimal in terms of both time and space complexity, given the problem constraints and the use of Python's built-in string operations. It leverages the index() method for efficient character lookup and string slicing for reversing and concatenation.

Big(O) Run-time Analysis

• Time Complexity: O(n)
  • word.index(ch): In the worst case, the index() method iterates through the entire string to find the character ch, or determines that it is not present. This operation takes O(n) time, where n is the length of the string word.
  • String slicing word[:index+1] and word[index+1:]: String slicing operations in Python typically take O(k) time, where k is the length of the slice. In this case, the slices are based on the index of the character, so in the worst case, it would still be bounded by O(n).
  • String reversal prefix[::-1]: Creating a reversed copy of the prefix also takes O(k) time, where k is the length of the prefix (at most n). Therefore, this is also bounded by O(n).
  • String concatenation: String concatenation operations are generally O(n) where n is the length of the new string.
  • Overall: The dominant operation is the index() method and the string reversal which take O(n) time. Therefore, the overall time complexity is O(n).

Big(O) Space Usage Analysis

• Space Complexity: O(n)
  • prefix = word[:index+1]: A new string prefix is created, which, in the worst case, can be a copy of the entire word string (if ch is the last character or not present). This takes O(n) space.
  • reversed_prefix = prefix[::-1]: A new reversed string reversed_prefix is created, which also takes O(k) space, where k is the length of the prefix (at most n). Therefore, this is bounded by O(n).
  • The rest of the operations involve concatenating strings, which create new strings. However, the space for these new strings is already accounted for in the reversed_prefix and original string. The space used is proportional to the length of the input string word.
  • Overall: The dominant space usage comes from creating the reversed prefix, which takes O(n) space. Therefore, the overall space complexity is O(n).

Edge Cases

1. Empty String:
   • If the input word is an empty string, the index() method will raise a ValueError because an empty string cannot contain any character. The try...except block handles this case, returning the original empty string. The function correctly handles an empty string input.
2. Character Not Found:
   • If the character ch is not found in the string word, the index() method raises a ValueError. The except block catches this exception and returns the original string word unchanged, as specified in the problem description. This is correctly handled.
3. Character at the Beginning:
   • If the character ch is the first character of the string word, the prefix to be reversed is just the first character. The function correctly reverses this single-character prefix and concatenates it with the rest of the string, resulting in the original string.
4. Character at the End:
   • If the character ch is the last character of the string word, the prefix to be reversed is the entire string. The function correctly reverses the entire string and returns the reversed string.
5. String with Only One Character:
   • If the string word contains only one character, and that character matches ch, the function correctly reverses the single-character string (which remains the same) and returns it.
6. String with Duplicate Characters:
   • If the string word contains multiple occurrences of the character ch, the function only reverses the prefix up to the first occurrence of ch, as required. The rest of the string remains unchanged.