Welcome to Subscribe On Youtube

541. Reverse String II

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

1. Convert String to List: The string s is converted into a list of characters, t. This conversion is necessary because strings in Python are immutable, meaning they cannot be changed after creation. Working with a list allows for the modification of individual characters.

2. Loop Through Chunks: The for loop iterates through the list t in steps of 2k (k << 1). The << operator is a bitwise left shift, effectively multiplying k by 2. This step size is chosen because the task is to reverse every k characters in segments of 2k characters, applying the reverse operation only to the first k characters of each segment.

3. Reverse Each Segment: Inside the loop, the slice t[i : i + k] is reversed. The slice selects the first k characters of the current 2k-character segment starting from index i. The reversed function returns an iterator that yields the characters in reverse order. This reversed slice is then assigned back to the original slice location in t, effectively reversing the characters in place.

4. Join and Return: Finally, the list of characters t is joined back into a string using ''.join(t) and returned.

Example

Let’s consider an example to illustrate the process:

• Suppose s = "abcdefg" and k = 2.
• The list t will initially be ['a', 'b', 'c', 'd', 'e', 'f', 'g'].
• The loop iterates in steps of 4 (k << 1 = 4), meaning it will process the slices t[0:2] and t[4:6].
• In the first iteration, t[0:2] is ['a', 'b'], which gets reversed to ['b', 'a'].
• No changes are made to t[2:4], so it remains ['c', 'd'].
• In the second iteration, t[4:6] is ['e', 'f'], which gets reversed to ['f', 'e'].
• The last character g does not have a counterpart to form a complete k segment, so it remains unchanged.
• The final list t is ['b', 'a', 'c', 'd', 'f', 'e', 'g'], which is then joined and returned as "bacdfeg".

• Java
• C++
• Python
• Go

• class Solution {
      public String reverseStr(String s, int k) {
          char[] chars = s.toCharArray();
          for (int i = 0; i < chars.length; i += (k << 1)) {
              for (int st = i, ed = Math.min(chars.length - 1, i + k - 1); st < ed; ++st, --ed) {
                  char t = chars[st];
                  chars[st] = chars[ed];
                  chars[ed] = t;
              }
          }
          return new String(chars);
      }
  }
  

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

• '''
  class range(start, stop, step=1)
  
  >>> k = 1
  >>> for i in range(0, 9, k):
  ...     print(i)
  ...
  0
  1
  2
  3
  4
  5
  6
  7
  8
  
  
  >>> for i in range(0, 9, k << 1):
  ...     print(i)
  ...
  0
  2
  4
  6
  8
  '''
  class Solution:
      def reverseStr(self, s: str, k: int) -> str:
          t = list(s)
          for i in range(0, len(t), k << 1): # protected from out-of-index error
              t[i : i + k] = reversed(t[i : i + k])
          return ''.join(t)
  
  ############
  
  class Solution(object):
    def reverseStr(self, s, k):
      """
      :type s: str
      :type k: int
      :rtype: str
      """
      cnt = 0
      isFirst = True
      a = ""
      b = ""
      ans = []
      for c in s:
        if isFirst:
          a = c + a
        else:
          b += c
        cnt += 1
        if cnt == k:
          if isFirst:
            ans.append(a)
            a = ""
          else:
            ans.append(b)
            b = ""
          isFirst = not isFirst
          cnt = 0
      return "".join(ans) + a + b
  
  

• func reverseStr(s string, k int) string {
  	t := []byte(s)
  	for i := 0; i < len(t); i += (k << 1) {
  		for st, ed := i, min(i+k-1, len(t)-1); st < ed; st, ed = st+1, ed-1 {
  			t[st], t[ed] = t[ed], t[st]
  		}
  	}
  	return string(t)
  }
  

All Problems

All Solutions