Reverse String II

• LeetCode: Reverse String II

• Problem:

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.

• Restrictions:

1. The string consists of lower English letters only.

2. Length of the given string and k will in the range [1, 10000]

• Examples:

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

• Analysis:

According to problem, reverse the first k characters for every 2k characters and less than 2k but greater than k.

For every k, it will be [reverse, non-reverse, reverse, non-reverse,....]

• Code - Java:

public class Solution {
    public String reverseStr(String s, int k) {
        int len = s.length();
        StringBuilder builder = new StringBuilder();
        int left = 0;
        boolean rev = false;
        for (int i = 0; i < len; i++) {
            if (i % k == 0) {
                String subStr = s.substring(left, i);
                if (rev) {
                    subStr = new StringBuilder(subStr).reverse().toString();
                }
                builder.append(subStr);
                left = i;
                rev = !rev;
            }
        }
        String subStr = s.substring(left, len);
        if (rev) {
            subStr = new StringBuilder(subStr).reverse().toString();
        }
        builder.append(subStr);
        return builder.toString();
    }
}

• Code - C++:

class Solution {
public:
    string reverseStr(string s, int k) {
        int len = s.length();
        string builder ="";
        int left = 0;
        bool rev = false;
        for (int i = 0; i < len; i++) {
            if (i % k == 0) {
                string subStr = s.substr(left, i - left);
                if (rev) {
                    reverse(subStr.begin(), subStr.end());
                }
                builder += subStr;
                left = i;
                rev = !rev;
            }
        }
        string subStr = s.substr(left, len - left);
        if (rev) {
            reverse(subStr.begin(), subStr.end());        
        }
        builder += subStr;
        return builder;
    }
};

• Code - Python:

class Solution(object):
    def reverseStr(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        sLen = len(s)
        builder = ""
        left = 0
        rev = False
        for i in range(sLen):
            if i % k == 0:
                subStr = s[left:i]
                if rev:
                    subStr = subStr[::-1]
                builder += subStr
                left = i
                rev = not rev
        subStr = s[left:sLen]
        if rev:
            subStr = subStr[::-1]
        builder += subStr
        return builder

• Time Complexity: O(N), N is the length of string s

• Space Complexity: O(N), N is the length of string s