Skip to content

Latest commit

 

History

History
67 lines (52 loc) · 1.86 KB

541. Reverse String II.md

File metadata and controls

67 lines (52 loc) · 1.86 KB

1. Description

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less 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 left the other as original.

Example:

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

Restrictions:

  1. The string consists of lower English letters only.
  2. Length of the given string and k will in the range [1, 10000]

2. Solutions

Solution 1: Language: C Mathematics Method to Split, Brute Force

Refer to the diagram below.

  • Tuesday, 25 August, 2020
  • Time Complexity: Not sure. Might be $O(k \times n)$
  • Space Complexity: $O(1)$
  • Runtime: 0 ms, faster than 100.00% of C online submissions for Reverse String II.
  • Memory Usage: 6.1 MB, less than 100.00% of C online submissions for Reverse String II.
void reverseString(char *s, int head, int tail) {
    while (head < tail) {
        // Swapping two characters.
        int temp = s[head];
        s[head] = s[tail];
        s[tail] = temp;
        head++;
        tail--;
    }
}

char *reverseStr(char *s, int k) {
    // See the diagram for help.
    int groups = strlen(s) / (2 * k);
    int n = 0;
    // Reverse substrings until the remainder less than 2k;
    while (n < groups) {
        reverseString(s, 2 * k * n, 2 * k * n + k - 1);
        n++;
    }
    // k > remainder;
    if (strlen(s) % (2 * k) < k) {
        reverseString(s, 2 * k * n, strlen(s) - 1);
    // 2k > remainder > k.
    } else {
        reverseString(s, 2 * k * n, 2 * k * n + k - 1);
    }
    return s;
}

3. Missing Complexity

  • Complexity: $O(n)$, $O(k * n)$ or $O(n^{2})$?