algoadvance

Leetcode 541. Reverse String II

Problem Statement

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.

Clarifying Questions

1. Is the input string composed of only lowercase English letters?
   • Yes, the input string s will only contain lowercase English letters.
2. What is the expected output for the function?
   • The function should return the modified string after applying the described transformations.
3. What are the constraints on the length of the string s and the integer k?
   • The string s has a length of up to 10000 characters, and k is in the range from 1 to 10000.

Strategy

1. Iterate Over the String:
   • I will iterate over the string in chunks of 2k characters.
2. Reverse the First k Characters of Each Chunk:
   • For each chunk of 2k characters, I will reverse the first k characters. If a chunk has less than 2k characters left, the chunk will be accordingly smaller.
   • If the remaining characters are fewer than k, I will reverse all of them.
   • If they are more than k but fewer than 2k, I will reverse the first k characters while keeping the rest unchanged.
3. Concatenate the Results:
   • After processing each chunk, concatenate the results into the final string.

Code Implementation

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

std::string reverseStr(std::string s, int k) {
    int n = s.size();
    
    for (int start = 0; start < n; start += 2 * k) {
        // Determine the end of the current segment to process
        int end = std::min(start + k, n);
        
        // Reverse the first k characters in the current segment
        std::reverse(s.begin() + start, s.begin() + end);
    }
    
    return s;
}

Time Complexity

• Time Complexity: The time complexity of this solution is (O(n)), where (n) is the length of the string s. We are traversing the entire string one time and performing reversals on segments which are in total linear time operations.
• Space Complexity: The space complexity is (O(1)) additional space, as we are performing in-place modifications on the input string.

This implementation efficiently processes the string with the given constraints and correctly applies the required transformations.

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?