Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/541.html

541. Reverse String II

Level

Easy

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]

Solution

For the given integer k, find each group with size 2k and reverse the first k characters in each group. If the last group’s size is less than k, then reverse all the letters in the last group.

Transform the string to an array of characters, and do the reverse in each group. Finally, return a string from the array.

• Java
• C++
• Python
• Go

• public class Reverse_String_II {
  
      class Solution {
          public String reverseStr(String s, int k) {
  
              char[] a = s.toCharArray();
  
              for (int i = 0; i < a.length - 1; i = i + 2*k) {
  
                  int l = i;
                  int r = Math.min(a.length - 1, l + k - 1); // inclusive: start+k-1
  
                  while (l < r) {
                      char tmp = a[l];
                      a[l] = a[r];
                      a[r] = tmp;
                      l++;
                      r--;
                  }
              }
              return new String(a);
          }
      }
  }
  
  ############
  
  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)
  
  
  >>> for i in range(0, 9, k):
  ...     print(i)
  ...
  0
  1
  2
  3
  4
  5
  6
  7
  8
  
  
  >>> k = 1
  >>> 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)
  }
  
  func min(a, b int) int {
  	if a < b {
  		return a
  	}
  	return b
  }
  

All Problems

All Solutions