Reverse Prefix of Word

#871 Most AskedEasy

Reverse Prefix of Word #871 Most Asked

Easy

1 view

Topics:

StringsTwo Pointers

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

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `word` and the character `ch`?
If the character `ch` does not appear in the string `word`, should I return the original `word`?
Is the input string `word` guaranteed to contain only lowercase English letters?
Is the character `ch` guaranteed to be a lowercase English letter?
By 'reverse prefix', do you mean the substring from the beginning of `word` up to and including the first occurrence of `ch`, should be reversed?

Brute Force Solution

Approach

The brute force strategy for reversing a word's prefix involves checking the word character by character to see if we find a specified target. If we find the target, we reverse everything up to and including that target. If we don't find it, we return the original word.

Here's how the algorithm would work step-by-step:

Look at the very first letter of the word.
Is it the target letter we're looking for? If so, reverse the word from the beginning up to that letter, then stop and give back the reversed portion plus the rest of the word.
If the first letter wasn't our target, look at the second letter.
Again, check if the second letter is our target letter. If it is, reverse the word from the beginning up to this second letter, then stop and give back the reversed portion plus the rest of the word.
Keep doing this, moving one letter at a time through the word and checking if that letter is our target.
If we reach the end of the word and haven't found the target letter, it means it's not there. In this case, just give back the original word unchanged.

Code Implementation

def reverse_prefix_brute_force(word, character):
    for index in range(len(word)):
        # Check if the current character matches the target.
        if word[index] == character:

            # Reverse the prefix up to and including the target.
            prefix_to_reverse = word[:index + 1]
            reversed_prefix = prefix_to_reverse[::-1]

            # Concatenate reversed prefix with remaining part of word.
            remaining_word = word[index + 1:]
            return reversed_prefix + remaining_word

    # If the target is not found return the original word.
    return word

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the word of length n at most once to find the target character. If the target character is found at index k (where k <= n), a reversal operation is performed on the prefix of length k+1. String reversal takes O(k) time. In the worst case, the target is the last character, making k = n-1. Therefore, the iteration takes O(n) time and the reversal takes O(n) time, resulting in a total time complexity of O(n) + O(n) = O(n).

Space Complexity

O(1) – The described algorithm operates directly on the input string and might reverse a portion of it in place or construct a new reversed string. However, it does not explicitly mention the usage of auxiliary data structures like arrays, lists, or hash maps that scale with the input string's length. It implies some constant extra memory used to store temporary variables for character comparison or possibly for swapping characters during the reversal. Thus, the auxiliary space complexity is constant, O(1), as it does not depend on the length of the input word.

Optimal Solution

Approach

The most efficient way to solve this problem is to first locate the target character in the word. If found, we reverse the portion of the word up to and including that character; otherwise, we return the original word.

Here's how the algorithm would work step-by-step:

Begin by searching for the specified character in the word.
If the character is not found, the original word remains unchanged, so return it immediately.
If the character is found, take the portion of the word from the beginning up to and including the located character.
Reverse this selected portion of the word.
Combine the reversed portion with the remainder of the original word (the part after the located character).
Return the resulting combined word which now has the prefix reversed.

Code Implementation

def reverse_prefix_of_word(word, character):
    string_length = len(word)
    character_index = -1

    for index in range(string_length):
        if word[index] == character:
            character_index = index
            break

    # If the target isn't found, there's nothing to reverse.
    if character_index == -1:
        return word

    # Extract the prefix up to and including the target character.
    prefix_to_reverse = word[:character_index + 1]

    # Reverse the prefix string.
    reversed_prefix = prefix_to_reverse[::-1]

    # Combine the reversed prefix with the rest of the string.
    remaining_string = word[character_index + 1:]
    result = reversed_prefix + remaining_string

    return result

Big(O) Analysis

Time Complexity

O(n) – Finding the target character requires, in the worst case, iterating through all n characters of the word. If the character is found, reversing the prefix, which is at most of length n, also takes O(n) time. Concatenating the reversed prefix and the remaining part of the string takes O(n) time. Since these operations are sequential and not nested, the overall time complexity is dominated by the linear operations, resulting in O(n).

Space Complexity

O(N) – The algorithm's space complexity is determined by the portion of the word that needs to be reversed. In the worst-case scenario, the target character could be the last character of the word, requiring a reversal of almost the entire word. This reversal typically involves creating a temporary copy or data structure, such as a list or a new string, to hold the reversed portion, where N is the length of the input word. The space needed for the reversed substring grows linearly with the length of the prefix to be reversed, hence O(N).

Edge Cases

Case	How to Handle
word is null or empty	Return the empty string directly, as there's nothing to reverse.
ch is not found in word	Return the original word unchanged, as no reversal is needed.
word contains only one character	If the single character matches ch, reverse the prefix which is just the same single character.
word contains only ch	Reverse the entire word (which is just the same character repeated) up to and including the last occurrence of ch.
ch is the first character of word	Reverse the first character (trivially the same character).
word is very long (close to maximum string length)	Ensure the algorithm does not exceed memory limitations by reversing the prefix in-place efficiently using StringBuilder or character array manipulation.
Multiple occurrences of ch exist in word	The algorithm should only reverse the prefix up to the first occurrence of ch.
ch is a special character (e.g., unicode, non-ASCII)	The character comparison should correctly handle unicode or non-ASCII characters.

word is null or empty

How to Handle:

Return the empty string directly, as there's nothing to reverse.

ch is not found in word

How to Handle:

Return the original word unchanged, as no reversal is needed.

word contains only one character

How to Handle:

If the single character matches ch, reverse the prefix which is just the same single character.

word contains only ch

How to Handle:

Reverse the entire word (which is just the same character repeated) up to and including the last occurrence of ch.

ch is the first character of word

How to Handle:

Reverse the first character (trivially the same character).

word is very long (close to maximum string length)

How to Handle:

Ensure the algorithm does not exceed memory limitations by reversing the prefix in-place efficiently using StringBuilder or character array manipulation.

Multiple occurrences of ch exist in word

How to Handle:

The algorithm should only reverse the prefix up to the first occurrence of ch.

ch is a special character (e.g., unicode, non-ASCII)

How to Handle:

The character comparison should correctly handle unicode or non-ASCII characters.