Reverse Prefix of Word

Problem Description

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.

Key Insights

• Identify the first occurrence of the character ch in the string word.
• If ch is found, reverse the substring from the start of word to the index of that occurrence.
• If ch is not found, return the original string unchanged.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string word, as we may need to traverse the entire string to find the character ch.

Space Complexity: O(1), since we are modifying the string in place without using additional data structures that scale with input size.

Solution

To solve this problem, we can follow these steps:

1. Traverse the string to find the index of the first occurrence of the character ch.
2. If ch is found, create a substring that includes the characters from the start of word to that index.
3. Reverse this substring.
4. Concatenate the reversed substring with the remainder of the original string starting from the character after the reversed segment.
5. Return the new string.

The main data structures used are strings for holding the original and modified text. The algorithm primarily relies on string slicing and the built-in reversing functionality.

Code Solutions