Lab $0($O$)$: Chars To The Left Of Me$,$ Integers To The

Right...

JUnit: P$2$J$14$Test.java

The two methods of this lab continue with the ongoing theme of strings, but this time operating at

the level of individual characters. Both of these problems were adapted from the ample offerings of

LeetCode, one of the premier collections of online coding challenges and automated testers beloved

by technical interviewers and job searching candidates. The JUnit test for this lab also uses the text

file warandpeace.txt as data source, so make sure to also copy this file in the root of your

project directory. Create a new class P$2$J$14$ in your project, and there first the static method

public static int$[]$ distanceFromCharacter$($String text, char c$)$

In the first method, you are given a text and some character c that is guaranteed to occur inside

the text at least once. This method should create and return an integer array the same length as

text so that each element gives the distance to the nearest occurrence of the character c from that

position. For example, the array returned for the argument "hello world" and the character

$\text{'}$o$\text{'}$ would be $\{4,3,2,1,0,1,1,0,1,2,3\}.$ If the character c had instead been

$\text{'}$e$\text{'},$ the returned array would be $\{1,0,1,2,3,4,5,6,7,8,9\}.$

Again, this problem could be solved in a simple $$Shlemiel$$ fashion with two nested loops. The outer

for$-$loop would iterate through the positions of the result array. For each such position, the inner

while$-$loop would advance left and right from that position in lockstep until it sees the first occurrence of the character c$.$ The grinding inefficiency of such a clumsy approach can be seen from any

text where the character c occurs as the first character, but nowhere else after that. The pain of

the quadratic running time becomes evident once the text length grows to the thousands.

To solve this problem in linear time, we note that the values of consecutive positions in the result

array cannot be just every which way but loose, but can differ from each other by at most one. This

allows you to use a single for$-$loop to fill in two temporary arrays left and right, that will then be

combined at the end of this method to produce the final result. Loop through the positions of

text to fill in the left array to fill in each element left$[$i$]$ with the distance to the nearest occurrence of the character c when you are allowed to go only left, but not right. To update these values in constant time, you should maintain an integer counter variable to keep track of this distance,

initialized to text.length$()+1.$ At every character other than the c that you are looking for, increment this counter by one, whereas at every occurrence of c$,$ bring that counter back to zero. The

current counter value becomes the value left$[$i$]$ being currently filled in$.$

Filling the values of right$[$i$]$ is done exactly the same way, except as a mirror image going from

right to left. You can either do this in a second loop for clarity, or combine both loops into one forloop with a bit of simple integer arithmetic for brevity $.$ Once you have filled in both arrays left

Page $42$ of $321$

and right, each element of the result array is the minimum of the left and right elements in

that position.

$($This same technique can also be used to solve a classic algorithm coding chestnut usually called

something like $$Trapping rainwater$,$ guaranteed to be found in some form in basically every algorithmic problem collection of this kind. The left and right arrays keep track of the tallest wall

seen to that direction from each position, filled in with a similar linear time for$-$loop that remembers the tallest wall that it has encountered so far. The height of the water pillar at each position is

then the minimum of the two values of the left and right arrays for that position.$)$

public static String pushDominoes$($String dominoes$)$

The second method is given a string parameter that represents a line of dominoes. Instead of placing these dominoes neatly on the table so that the pips match between consecutive dominoes like a

civilized person, this time we are being more whimsical and place these dominoes standing up to

create a chain of falling dominoes, itself a well$-$known metaphor for various things in life on both

personal and national scales.

In the dominoes string given as argument to this method, the character $\text{'}.\text{'}$ denotes a domino

standing still, the character $\text{'}$R$\text{'}$ denotes a domino falling right, and the character $\text{'}$L$\text{'}$ demotes a

domino falling left. The simulation of this domino chain proceeds in discrete time steps. In each

time step, every falling domino causes its neighbouring domino to the direction of falling to also become a falling domino, provided that that neighbour was still standing at that moment. If a standing

domino is simultaneously being pushed right by its left neighbour and pushed left by its right

neighbour, these two forces cancel each other out, and the domino will remain standing.