The end of my workday is approaching shortly. Hopefully I will be done with this post soon; otherwise will finish it tomorrow.
Earlier today I was snooping around in the LeetCode website. For the first time I ran into a page that shows every submission you make for a problem. Perhaps I am mistaken, but it seems that the site counts as attempts every submission you make. For example, you ran your first pass and let’s say it is accepted but you want to learn more by improving performance. You may even generate one or more implementations. It seems that they count against you. This seems awkward to me. If I am trying to learn I should not be penalized. If my assumption is incorrect, PLEASE LEAVE ME A NOTE BELLOW SETTING ME STRAIGHT.
I took a stab at LeetCode 541 Reverse String II problem.
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 left the other as original. Constraints: o 1 <= s.length <= 104 o s consists of only lowercase English letters. o 1 <= k <= 104
We are given a string `s` and an integer `k`. We need to reverse and append characters. Quite convoluted but there it is.
public String reverseStr(String s, int k) {
}
We are going to solve this problem using the Java programming language and the VSCode IDE on a Windows platform. Since Java is quite portable the platform and IDE of choice should not affect the code.
abcd 2 main <<< s ==>abcd<== main <<< k: 2 main <<< reverseStr0 ==>bacd<== main <<< reverseStr ==>bacd<== abcde 2 main <<< s ==>abcde<== main <<< k: 2 main <<< reverseStr0 ==>bacde<== main <<< reverseStr ==>bacde<== abcdefgh 3 main <<< s ==>abcdefgh<== main <<< k: 3 main <<< reverseStr0 ==>cbadefhg<== main <<< reverseStr ==>cbadefhg<== abcdefg 2 main <<< s ==>abcdefg<== main <<< k: 2 main <<< reverseStr0 ==>bacdfeg<== main <<< reverseStr ==>bacdfeg<== abcdef 2 main <<< s ==>abcdef<== main <<< k: 2 main <<< reverseStr0 ==>bacdfe<== main <<< reverseStr ==>bacdfe<== abcdefghijklmnopq 2 main <<< s ==>abcdefghijklmnopq<== main <<< k: 2 main <<< reverseStr0 ==>bacdfeghjiklnmopq<== main <<< reverseStr ==>bacdfeghjiklnmopq<== abcdefghijklmnopq 3 main <<< s ==>abcdefghijklmnopq<== main <<< k: 3 main <<< reverseStr0 ==>cbadefihgjklonmpq<== main <<< reverseStr ==>cbadefihgjklonmpq<== abcdefghijklmnopq 4 main <<< s ==>abcdefghijklmnopq<== main <<< k: 4 main <<< reverseStr0 ==>dcbaefghlkjimnopq<== main <<< reverseStr ==>dcbaefghlkjimnopq<==
We are provided two input lines. The first contains a sequence of lower case characters. The second line contains the value for `k`.
Our test code seems to read both input lines and assign them to variables `s` and `k`. Both variables are then displayed. This is done to verify that the input data matches the contents of our variables which will be shortly used as arguments to the function of interest.
It seems that the function of interest is called and the results are displayed. But wait, there is more. A second implementation that returns the same value is also called.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read string `s` ****
String s = br.readLine().trim();
// **** read `k` ****
int k = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< s ==>" + s + "<==");
System.out.println("main <<< k: " + k);
// **** generate and display answer ****
System.out.println("main <<< reverseStr0 ==>" + reverseStr0(s, k) + "<==");
// **** generate and display answer ****
System.out.println("main <<< reverseStr ==>" + reverseStr(s, k) + "<==");
}ot
Our test code seems to closely follow the description of a test case. Not much to add to it at this time.
/**
* 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 left the other as original.
*
* Runtime: 1 ms, faster than 77.39% of Java online submissions.
* Memory Usage: 39 MB, less than 60.02% of Java online submissions.
*
* 60 / 60 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 39 MB
*
* This implementation uses StringBuilders.
*/
static String reverseStr0(String s, int k) {
// **** initialization ****
int len = s.length();
StringBuilder ans = new StringBuilder();
int i = 0;
int twoK = 2 * k;
// **** take care of complete 2 * k sub strings ****
for ( ; i < len / twoK; i++) {
// **** extract sub string ****
String sub = s.substring(i * twoK, (i + 1) * twoK);
// **** first k characters ****
StringBuilder sb = new StringBuilder(sub.substring(0, k));
// **** reverse first k characters ****
sb.reverse();
// **** append last k characters ****
sb.append(sub.substring(k));
// **** append to answer ****
ans.append(sb);
}
// **** check if done ****
if (i * twoK == len)
return ans.toString();
// **** if fewer than k characters left (reverse all of them) ****
if (len - (i * twoK) < k) {
// **** extract the sub string ****
String sub = s.substring(i * twoK);
// **** entire sub string ****
StringBuilder sb = new StringBuilder(sub);
// **** reverse all characters ****
sb.reverse();
// **** append to answer ****
ans.append(sb);
}
// **** reverse the first k characters and leave the others unchanged ****
else {
// **** extract the sub string ****
String sub = s.substring(i * twoK);
// **** k first characters ****
StringBuilder sb = new StringBuilder(sub.substring(0, k));
// **** reverse all characters ****
sb.reverse();
// **** append remaining characters ****
sb.append(sub.substring(k));
// **** append to answer ****
ans.append(sb);
}
// **** return answer ****
return ans.toString();
}
We start by performing the initialization steps.
Before we proceed, the approach we are taking is to match the description with code. We are also using the StringBuilder class.
In the loop we take case of all the complete blocks of 2 * k characters.
Once we are done, we check if we are done. If so we return the string in the `ans` StringBuilder.
We now check if we have to reverse all the remaining characters. If so we do so and append the characters to the `ans` StringBuilder. If that is not the case, we reverse the first `k` characters and append the remaining.
Yes, you are correct, we could have further optimized the code (and get additional attempts at LeetCode). Both parts of the `if then else` statement reverse the first `k` characters, but only the `else` appends the remaining characters.
Please take a look at the comments section of this approach and note the execution time and space.
/**
* 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 left the other as original.
*
* Runtime: 1 ms, faster than 77.39% of Java online submissions.
* Memory Usage: 39.1 MB, less than 48.59% of Java online submissions.
*
* 60 / 60 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 39.1 MB
*
* This implementation uses a char array.
*/
static String reverseStr(String s, int k) {
// **** initialization ****
char[] ca = s.toCharArray();
// **** loop once per block of 2 * k characters ****
for (int i = 0; i < ca.length; i += 2 * k) {
// **** compute range to reverse characters ****
int begin = i;
int end = Math.min(i + k - 1, ca.length - 1);
// **** reverse characters ****
while (begin < end) {
char tmp = ca[begin];
ca[begin++] = ca[end];
ca[end--] = tmp;
}
}
// **** return string of character array ****
return String.valueOf(ca);
}
This is the second approach using a character array instead of StringBuilders.
We start by generating a char[] `ca` with the characters in the input string.
We then enter a loop that processes `2 * k` characters per pass.
We need to calculate begin and end values for the range of characters we need to reverse. Once that is done we enter a while loop that reverses the characters in the specified range.
When all is set and done we return the contents of the character array converted to a string.
This code is a lot shorter and perhaps easier to follow or perhaps not. Go back and read the requirements for this problem. In addition please read the comments section of this implementation. It seems both implementations execute is about the same time. Perhaps we so revisit the idea that StringBuilders are slower and loops are faster. BTW, do not base future decisions on a single test case. Experiment and come up with your own conclusion.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John