algoadvance

Given a 0-indexed string word and a character ch, reverse the segment of word that starts at the 0 index and ends at the index of the first occurrence of ch (inclusive). If the character ch does not exist in word, do nothing to the string.

• Return the resulting string after reversing the prefix.

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.
You should do nothing to the string.

Constraints:

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

Clarifying Questions

1. Can word contain duplicate characters?
   • Yes, the string can contain duplicate characters.
2. If the ch character is not in word, should we simply return the original word?
   • Yes, if ch is not found in the string, return the string as is.
3. Are all characters guaranteed to be lowercase English letters?
   • Yes, word consists of lowercase English letters, and ch is a lowercase English letter.

Strategy

1. Find the first occurrence of ch in word:
   • Use the string method index to find the position of ch. If ch is not found, handle the ValueError and return the original word.
2. Reverse the substring from the start to the found index:
   • Use slicing to segment the string into three parts: the part to reverse, the part after the reversed segment, and the segment to reverse itself. Concatenate these parts accordingly.
3. Edge Cases:
   • If ch is not present in word.
   • If word only contains one character.
   • If ch is at the very start of word.

Code

def reversePrefix(word: str, ch: str) -> str:
    try:
        # Find index of first occurrence of ch
        idx = word.index(ch)
        # Slice the word into two parts and reverse the first part
        return word[:idx + 1][::-1] + word[idx + 1:]
    except ValueError:
        # If ch is not found, return word as is
        return word

# Test cases
print(reversePrefix("abcdefd", "d"))    # Output: "dcbaefd"
print(reversePrefix("xyxzxe", "z"))     # Output: "zxyxxe"
print(reversePrefix("abcd", "z"))       # Output: "abcd"

Time Complexity

• The time complexity of this solution is O(n), where n is the length of the string word. This is primarily due to the slicing and reversing operations which each take O(k) time for the prefix of length k.
• The slicing and concatenation operations are efficient and run linearly with respect to the substring lengths.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?