I was planning on working a couple blocks (a block entails 2 hours) on this post but ran out of time. The reason for it is that I will be collaborating with a group by posting some of their articles in my blog. It appears that the group uses Google Docs to create the text for their posts. For text I use Microsoft Word and for diagrams Microsoft Visio.
I have never before directly included a Google Docs on WordPress. That is the reason I had to learn the process, and check for possible caveats. That took some additional effort and time. If interested it seem that the section Use Google Docs to Post to WordPress on Resource Center provides the necessary steps.
Posting to WordPress from Google Docs is easy with the add-on for WordPress.com (Jetpack). Before continuing, make sure you have a free Google/Gmail account, that Jetpack is installed and configured on your WordPress site, and that you have registered with a WordPress.com account through Jetpack.
Make sure you take into accounts the prerequisites paragraph in the section in question. I just made sure I complied. At this time I am using the FREE version of Jetpack for WordPress. I am considering a paid subscription but have not committed to it yet.
For the main topic of this post, I solved the LeetCode problem 763 Partition Labels. It took me a few minutes to understand the requirements. Given that I 
was under pressure to get this post done, I should have worked my approach for a few more minutes before generating my first pass. I started a second approach by eliminating some upfront work that was not really needed. At some point I just stopped. As we go through the description it will become obvious how to improve on it. That said, both approaches were accepted.
A string S of lowercase English letters is given.
We want to partition this string into as many parts as possible
so that each letter appears in at most one part,
and return a list of integers representing the size of these parts.
Note:
S will have length in range [1, 500].
S will consist of lowercase English letters ('a' to 'z') only.
I have included a simple test scaffold due to the fact that I like the simplicity of working on my computer. I decided to use the Java programming language and the VSCode IDE on a Windows 10 machine. As long as you use Java the IDE or platform should not interfere with the results.
class Solution {
public List<Integer> partitionLabels(String S) {
}
}
As illustrated, the function that we have to produce takes a single string as a parameter.
ababcbacadefegdehijhklij main <<< S ==>ababcbacadefegdehijhklij<== length: 24 main <<< partitionLabels0: [9, 7, 8] main <<< partitionLabels: [9, 7, 8] eccbbbbdec main <<< S ==>eccbbbbdec<== length: 10 main <<< partitionLabels0: [10] main <<< partitionLabels: [10]
I seems like we need to specify an input string which we will read and display. In addition the test scaffolding displays the length of the string. We then call a couple functions which seem to produce the same results.
Both examples come from LeetCode. The first is provides as an example. The second is due to a mistake in my initial code.
With this in mind, let’s dive into the test scaffolding code.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read string ****
String S = sc.nextLine().trim();
// **** close scanner ****
sc.close();
// ???? ????
System.out.println("main <<< S ==>" + S + "<== length: " + S.length());
// **** partition and display sizes ****
System.out.println("main <<< partitionLabels0: " + partitionLabels0(S));
// **** partition and display sizes ****
System.out.println("main <<< partitionLabels: " + partitionLabels(S));
}
We open a scanner, read the text string, close the scanner, display the string and length and then call two versions of the function. The output is displayed. Note that what we need to do is return the length of each set. In the first example there are three sets. The results are explained in the LeetCode web page with the requirements for the problem.
/**
* A string S of lowercase English letters is given.
* We want to partition this string into as many parts as possible
* so that each letter appears in at most one part,
* and return a list of integers representing the size of these parts.
*/
static List<Integer> partitionLabels0(String S) {
// **** for results ****
List<Integer> sizes = new ArrayList<Integer>();
// **** first and last positions of characters in S ****
TreeMap<Character, Integer> firstPos = new TreeMap<Character, Integer>();
TreeMap<Character, Integer> lastPos = new TreeMap<Character, Integer>();
// **** populate the first and last position of all characters ****
for (int i = 0; i < S.length(); i++) {
char ch = S.charAt(i);
firstPos.putIfAbsent(ch, i);
if (lastPos.get(ch) == null)
lastPos.put(ch, i);
else
lastPos.replace(ch, lastPos.get(ch), i);
}
// **** instead of lastPos hash map ****
int[] lastIndex = new int[26];
for (int i = 0; i < S.length(); i++)
lastIndex[S.charAt(i) - 'a'] = i;
// **** first min and max ****
int min = firstPos.get(S.charAt(0));
int max = lastPos.get(S.charAt(0));
// **** traverse S ****
int l = 0;
int r = 0;
for (int i = 1; i < S.length() && (r < S.length() - 1); i++) {
// **** ****
char ch = S.charAt(i);
l = firstPos.get(ch);
r = lastIndex[ch -'a'];
// **** update min and max (if left > max) ****
if (l > max) {
// **** compute size and add to list ****
sizes.add(max - min + 1);
// **** update min and max ****
min = firstPos.get(ch);
max = lastIndex[ch - 'a'];
} else if (r > max) {
max = r;
}
}
// **** compute size and add to list ****
sizes.add(max - min + 1);
// **** return list of sizes ****
return sizes;
}
As I mentioned before, my initial idea was correct, but I should have given it more thought. What we need to do is specify a range in which a sub set of characters with the specified requirements can be defined. I thought to specify a range which will include the start and end characters. For that I needed the initial and ending positions. This makes sense, but there is no need to keep track of the starting positions because we will be getting when we traverse the string for a second time.
We first declare a list of Integers in which we will return the results. I then decided to use a Tree Map to track the starting and ending positions of the characters in the string. Note that we only need to generate the position for the ending characters. Since there are only 26 lower case characters, we could have used a simple array instead of a Tree Map.
We the traverse the string for the first time and populate the two tree maps. I had a couple statements (which I removed from the source code) to visualize what I was doing. At some point after my first approach was accepted, I incorrectly started to edit the solution. That was my mistake. I should have moved to a second instance of this function.
I then decided that as we traversed the input string, we would have to check and update a range in which the set of characters would fit. With additional though, we only need to update the right side of the range.
We then loop through the input string a second time. This makes the runtime execution O(2 * n). Note that when the current character is outside the range, we store the count of the current range, and reset it with a new range expressed like min and max limits.
When all is wet and done, we need to make sure we did not miss the last range.
/**
* A string S of lowercase English letters is given.
* We want to partition this string into as many parts as possible
* so that each letter appears in at most one part,
* and return a list of integers representing the size of these parts.
*
* Execution time O(n * 2)
*
* Runtime: 7 ms, faster than 23.91% of Java online submissions.
* Memory Usage: 39 MB, less than 37.43% of Java online submissions.
*/
static List<Integer> partitionLabels(String S) {
// **** for results ****
List<Integer> sizes = new ArrayList<Integer>();
// **** first position of characters in S ****
TreeMap<Character, Integer> firstPos = new TreeMap<Character, Integer>();
// **** populate the first and last position of all characters ****
for (int i = 0; i < S.length(); i++)
firstPos.putIfAbsent(S.charAt(i), i);
// **** instead of lastPos hash map ****
int[] lastIndex = new int[26];
for (int i = 0; i < S.length(); i++)
lastIndex[S.charAt(i) - 'a'] = i;
// **** first min and max ****
int min = firstPos.get(S.charAt(0));
int max = lastIndex[S.charAt(0) - 'a'];
// **** traverse S ****
int l = 0;
int r = 0;
for (int i = 1; i < S.length() && (r < S.length() - 1); i++) {
// **** ****
char ch = S.charAt(i);
l = firstPos.get(ch);
r = lastIndex[ch -'a'];
// **** update min and max (if left > max) ****
if (l > max) {
// **** compute size and add to list ****
sizes.add(max - min + 1);
// **** update min and max ****
min = firstPos.get(ch);
max = lastIndex[ch - 'a'];
} else if (r > max) {
max = r;
}
}
// **** compute size and add to list ****
sizes.add(max - min + 1);
// **** return list of sizes ****
return sizes;
}
This last function is quite similar to the previous one. Note that I have removed the last position tree map and replaced it with the lastIndex array. Also note that the array contains positions for all possible lower case characters. We only populate the positions for the characters in our input string.
As you can see, the code is similar and seems like I left the code incomplete. Sorry about that. With some additional thought, I would recommend generating a third and final pass. You should be able to have simpler and faster code. At this time I will leave it to you to generate such pass. If you decide to do so, please leave me a message and I will include it in an edited version of the post.
My wife and I decided to get some additional groceries to stock our outside refrigerator and freezer. I will comment on the reason that prompted us to go shopping in a future post.
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, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 2952 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa