This is the 20th day of my participation in the August Text Challenge.More challenges in August

541. Reverse string II

Given a string s and an integer k, invert the first K characters for every 2k characters from the beginning of the string.

If there are less than k characters left, all the remaining characters are reversed. If the remaining characters are less than 2K but greater than or equal to K, the first K characters are reversed and the remaining characters are left as is.

Example 1:

Input: s = "abcdefg", k = 2 Output: "bacdfeg"Copy the code

Example 2:

Input: s = "abcd", k = 2Copy the code

 

Tip:

1 <= S. length <= 104 s Consists of lowercase English only. 1 <= k <= 104Copy the code

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 left the other as original.

 

Example 1:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"
Copy the code

Example 2:

Input: s = "abcd", k = 2
Output: "bacd"
Copy the code

  Constraints:

1 <= s.length <= 104
s consists of only lowercase English letters.
1 <= k <= 104
Copy the code

Their thinking

We simulate directly as the problem implies: invert each substring of length Kk starting with a multiple of 2k2k. If the substring length is less than kk, the entire substring is reversed. Complexity analysis

Time complexity: O(n)O(n), where nn is the length of the string ss.

Spatial complexity: O(1)O(1) or O(n)O(n), depending on the nature of the string type in the language used. If the string is modifiable, then we can modify it directly on the original string, O(1)O(1), otherwise we need O(n)O(n) O(n) space to temporarily convert the string to modifiable data structures (such as arrays), O(n)O(n) O(n).

code

var reverseStr = function(s, k) { const n = s.length; const arr = Array.from(s); for (let i = 0; i < n; i += 2 * k) { reverse(arr, i, Math.min(i + k, n) - 1); } return arr.join(''); }; const reverse = (arr, left, right) => { while (left < right) { const temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; }}Copy the code