algoadvance

Leetcode 2000. Reverse Prefix of Word

Problem Statement

2000. Reverse Prefix of Word

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

Return the resulting string.

Example

1. Input: word = "abcdefd", ch = 'd' Output: "dcbaefd"

2. Input: word = "xyxzxe", ch = 'z' Output: "zxyxxe"

3. Input: word = "abcd", ch = 'z' Output: "abcd"

Clarifying Questions

1. Case Sensitivity: Is the character comparison case-sensitive?
   • Yes, it is case-sensitive.
2. Length of Input: Are there any constraints on the length of the word string?
   • The length of word is in the range [1, 250].
3. Character Existence: What should the function return if the character does not exist in the word?
   • The function should return the word unchanged.

Strategy

1. Find the Index: Locate the first occurrence of the character ch in the string word.
2. Reverse the Prefix: If the character is found, reverse the substring from the beginning of word to the index of ch.
3. Concatenate: Concatenate the reversed prefix with the remainder of the string and return.

Steps:

1. Use find to locate the index of ch in word.
2. If ch is not found, return word as is.
3. If ch is found, reverse the substring from the beginning of word to the index (inclusive).
4. Concatenate the reversed prefix with the rest of the string and return the result.

Code

#include <iostream>
#include <string>
#include <algorithm> // For std::reverse

std::string reversePrefix(std::string word, char ch) {
    // Find the first occurrence of ch
    size_t index = word.find(ch);
    
    // If ch is found, reverse the prefix
    if (index != std::string::npos) {
        // Reverse the substring from the beginning to the index, inclusive
        std::reverse(word.begin(), word.begin() + index + 1);
    }
    
    // Return the modified word (or the original word if ch was not found)
    return word;
}

// Example usage
int main() {
    std::string word = "abcdefd";
    char ch = 'd';
    std::cout << reversePrefix(word, ch) << std::endl; // Output: "dcbaefd"

    word = "xyxzxe";
    ch = 'z';
    std::cout << reversePrefix(word, ch) << std::endl; // Output: "zxyxxe"

    word = "abcd";
    ch = 'z';
    std::cout << reversePrefix(word, ch) << std::endl; // Output: "abcd"

    return 0;
}

Time Complexity

• Finding the Index: The find function runs in O(n) time, where n is the length of the string word.
• Reversing the Substring: The reverse function also runs in O(k) time, where k is the length of the prefix being reversed. In the worst case, k = n.

Combining both, the overall time complexity is O(n).

Space Complexity

• The space complexity is O(1) extra space since only a few indexing variables are used, and operations are done in place. The input object word is modified and returned, but no additional data structures proportional to the input size are utilized.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?