LeetCode 0541. Reverse String II Solution in Java, C++, Python & More | Explanation + Code

Description

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.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= s.length <= 104
• s consists of only lowercase English letters.
• 1 <= k <= 104

Solutions

Solution 1: Two Pointers

We can traverse the string s, iterating over every 2k characters, and then use the two-pointer technique to reverse the first k characters among these 2k characters.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.

PythonJavaC++GoTypeScript

class Solution: def reverseStr(self, s: str, k: int) -> str: cs = list(s) for i in range(0, len(cs), 2 * k): cs[i : i + k] = reversed(cs[i : i + k]) return "".join(cs)(code-box)

class Solution { public String reverseStr(String s, int k) { char[] cs = s.toCharArray(); int n = cs.length; for (int i = 0; i < n; i += k * 2) { for (int l = i, r = Math.min(i + k - 1, n - 1); l < r; ++l, --r) { char t = cs[l]; cs[l] = cs[r]; cs[r] = t; } } return new String(cs); } }(code-box)

class Solution { public: string reverseStr(string s, int k) { int n = s.size(); for (int i = 0; i < n; i += 2 * k) { reverse(s.begin() + i, s.begin() + min(i + k, n)); } return s; } };(code-box)

func reverseStr(s string, k int) string { cs := []byte(s) n := len(cs) for i := 0; i < n; i += 2 * k { for l, r := i, min(i+k-1, n-1); l < r; l, r = l+1, r-1 { cs[l], cs[r] = cs[r], cs[l] } } return string(cs) }(code-box)

function reverseStr(s: string, k: number): string { const n = s.length; const cs = s.split(''); for (let i = 0; i < n; i += 2 * k) { for (let l = i, r = Math.min(i + k - 1, n - 1); l < r; l++, r--) { [cs[l], cs[r]] = [cs[r], cs[l]]; } } return cs.join(''); }(code-box)