String Algorithm: Reverse the first k characters for every 2k characters

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:
The string consists of lower English letters only.
Length of the given string and k will in the range [1, 10000]

The problem statement is actually a bit hard to understand, but once you get it, this problem is easy to solve.

How to Reverse string in C++ using std::reverse for the first k characters?

The std::C++ has a handy reverse method that takes two iterators, and reverse it. Thus, we can iterate from the start, and increment the step of 2*k, compute the range, which is then passed to the reverse function to do the work.

1
2
3
4
5
6
7
8
9
10

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

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

You can also use a two pointer to swap until they meet in the middle.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k) {
            int a = i, b = min(i + k, (int)s.size());
            int left = a, right =  b - 1;
            while (left < right) {
                swap(s[left ++], s[right --]);
            }
        }
        return s;
    }
};

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k) {
            int a = i, b = min(i + k, (int)s.size());
            int left = a, right =  b - 1;
            while (left < right) {
                swap(s[left ++], s[right --]);
            }
        }
        return s;
    }
};

Other string reversing algorithms:

• How to Reverse Words in a String in Place using C++ std::reverse?
• How to Reverse Words in a String?
• How to Reverse Only Letters in a String?
• How to Reverse Vowels of a String in C/C++?
• Reverse String in C/C++

–EOF (The Ultimate Computing & Technology Blog) —