algoadvance

Leetcode 541. Reverse String II

Problem Statement

541. Reverse String II

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.

Examples:

  1. Input: s = "abcdefg", k = 2 Output: "bacdfeg"

  2. Input: s = "abcd", k = 2 Output: "bacd"

Clarifying Questions

  1. Q: Are there any constraints on the value of k or the length of string s? A: The length of s will be between 1 and 10000. k will be a positive integer.

  2. Q: What are the characters contained in the string s? A: The string s consists of lower English letters only.

Strategy

  1. Iterate over the string s in chunks of 2k.
  2. For each chunk:
    • Reverse the first k characters.
    • Leave the rest 2k - k characters as they are.
  3. If any chunk has fewer than k characters left, simply reverse them.

Code

Let’s implement this now:

public class Solution {
    public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();
        for (int start = 0; start < arr.length; start += 2 * k) {
            int i = start, j = Math.min(start + k - 1, arr.length - 1);
            while (i < j) {
                char temp = arr[i];
                arr[i++] = arr[j];
                arr[j--] = temp;
            }
        }
        return new String(arr);
    }

    // Main method for testing
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.reverseStr("abcdefg", 2)); // Output: "bacdfeg"
        System.out.println(sol.reverseStr("abcd", 2));    // Output: "bacd"
    }
}

Explanation of Code

  1. Convert the string s to a character array arr to allow in-place modifications.
  2. Iterate through the character array in increments of 2 * k.
  3. For each segment of 2 * k:
    • Reverse the first k characters using two pointers technique.
    • Adjust the pointers until i meets j to ensure the segment is reversed properly.
  4. Convert the character array back to a string and return the result.

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the length of the string s:

The space complexity is (O(n)) only due to the conversion of the string to a character array, which is necessary to perform in-place modification in Java. Apart from this, the algorithm uses a constant amount of extra space for variables.

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