Good morning! It is a cold and dark Sunday morning in the Twin Cities of Minneapolis and St. Paul in Minnesota. The silver lining is that the forecast for today calls for a high temperature of 80F. Perfect day for grilling outside and perhaps drink one or two adult beverages.
After finishing my 2-hour block, my wife and I will complete our grocery shopping by stopping by Trader Joe’s in St. Paul. It seems that lately we are doing groceries every other weekend. That saves around five gallons of gasoline every month.
It is too early (dark and cold) for box elder bugs to be out and about. As it gets warmer they seem to appear from nowhere. We are planning on grilling outside so they will become a nuisance. In the afternoon hours most homes in our area have a few hundred box elder bugs on the walls. As long as we do not have to interact with them, let them be.
I took a look at HackerRank: Short Palindrome. It seems that problems are getting harder and perhaps less realistic of what a software engineer will encounter in real life. This one was rated with difficulty: Medium.
Consider a string, s, of n `lowercase` English letters where each character, s[i] (0 <= i < n), denotes the letter at index i in s. We define an (a,b,c,d) palindromic tuple of s to be a sequence of indices in s satisfying the following criteria: o s[a] = s[d], meaning the characters located at indices a and d are the same. o s[b] = s[c], meaning the characters located at indices b and b are the same. o 0 <= a < b < c < d < s, meaning that a, b, c, and d are ascending in value and are valid indices within string s. Given s, find and print the number of (a,b,c,d) tuples satisfying the above conditions. As this value can be quite large, print it modulo (10^9 + 7). Lowercase is the description given to small letters, as opposed to capital letters. For example, the word yes is in all lowercase letters, whereas the word YES is in all uppercase letters. Capital letters were usually stored in a higher (or upper) case, and small letters were usually stored below in a lower case. Constraints: o 1 <= |s| <= 10^6 o It is guaranteed that s only contains lowercase English letters.
We are given a string in lowercase English characters. There are 26 lowercase characters.
We need to find palindromes of four characters in the specified string. But wait, there is a restriction. The letters may or may not be consecutive.
If interested in this problem, I suggest for you to go to the HackerRank web site and read the current description of the problem before attempting to solve it. Not sure if the text for problems changes over time.
In this post we will attempt to solve the problem using the Java programming language and the VSCode IDE on a Windows computer. Because of this we will also have to include test code. Unless you wish to keep the solution and test code together, it is simpler to attempt solving problems using the on-line IDE provided by HackerRank.
/*
* Complete the 'shortPalindrome' function below.
*
* The function is expected to return an INTEGER.
* The function accepts STRING s as parameter.
*/
public static int shortPalindrome(String s) {
// Write your code here
}
The signature of the function of interest is simple. We are given a string of lowercase English characters and are supposed to return the count of 4-letter palindromes.
aeea main <<< s ==>aeea<== <<< i: 0 c: a <<< ans: 0 <<< arr3: [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr2: [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr1: [1, 0, 0, 0, 0] <<< i: 1 c: e <<< ans: 0 <<< arr3: [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr2: [0, 1, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr1: [1, 1, 0, 0, 0] <<< i: 2 c: e <<< ans: 0 <<< arr3: [0, 1, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr2: [0, 2, 0, 0, 0] [0, 1, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr1: [1, 2, 0, 0, 0] <<< i: 3 c: a <<< ans: 0 arr3[0][1]: 1 <<< ans: 1 <<< arr3: [0, 1, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr2: [1, 2, 0, 0, 0] [2, 1, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr1: [2, 2, 0, 0, 0] main <<< ans: 1 eeeeeeu main <<< s ==>eeeeeeu<== <<< i: 0 c: e <<< ans: 0 <<< arr3: [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr2: [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr1: [0, 1, 0, 0, 0] <<< i: 1 c: e <<< ans: 0 <<< arr3: [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr2: [0, 0, 0, 0, 0] [0, 1, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr1: [0, 2, 0, 0, 0] <<< i: 2 c: e <<< ans: 0 <<< arr3: [0, 0, 0, 0, 0] [0, 1, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr2: [0, 0, 0, 0, 0] [0, 3, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr1: [0, 3, 0, 0, 0] <<< i: 3 c: e <<< ans: 0 arr3[1][1]: 1 <<< ans: 1 <<< arr3: [0, 0, 0, 0, 0] [0, 4, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr2: [0, 0, 0, 0, 0] [0, 6, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr1: [0, 4, 0, 0, 0] <<< i: 4 c: e <<< ans: 1 arr3[1][1]: 4 <<< ans: 5 <<< arr3: [0, 0, 0, 0, 0] [0, 10, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr2: [0, 0, 0, 0, 0] [0, 10, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr1: [0, 5, 0, 0, 0] <<< i: 5 c: e <<< ans: 5 arr3[1][1]: 10 <<< ans: 15 <<< arr3: [0, 0, 0, 0, 0] [0, 20, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr2: [0, 0, 0, 0, 0] [0, 15, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr1: [0, 6, 0, 0, 0] <<< i: 6 c: u <<< ans: 15 <<< arr3: [0, 0, 0, 0, 0] [0, 20, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr2: [0, 0, 0, 0, 0] [0, 15, 0, 0, 6] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] <<< arr1: [0, 6, 0, 0, 1] main <<< ans: 15
We are given a single input line that contains the string to be processed. Our test code seems to be able to read the string and for testing purpose display it. Since the input matches the output we are ready to call the function of interest.
The answer for each of the two test cases is displayed as the last line on each sequence. I created these test cases. I thought it would be simple to deal with lowercase vowels (just 5) instead of lowercase characters (26). Please keep this in mind while looking at the debugging statements.
abba main <<< s ==>abba<== <<< i: 0 c: 0 <<< ans: 0 <<< i: 1 c: 1 <<< ans: 0 <<< i: 2 c: 1 <<< ans: 0 <<< i: 3 c: 0 <<< ans: 0 arr3[0][1]: 1 <<< ans: 1 main <<< ans: 1 kkkkkkz main <<< s ==>kkkkkkz<== <<< i: 0 c: 10 <<< ans: 0 <<< i: 1 c: 10 <<< ans: 0 <<< i: 2 c: 10 <<< ans: 0 <<< i: 3 c: 10 <<< ans: 0 arr3[10][10]: 1 <<< ans: 1 <<< i: 4 c: 10 <<< ans: 1 arr3[10][10]: 4 <<< ans: 5 <<< i: 5 c: 10 <<< ans: 5 arr3[10][10]: 10 <<< ans: 15 <<< i: 6 c: 25 <<< ans: 15 main <<< ans: 15 ghhggh main <<< s ==>ghhggh<== <<< i: 0 c: 6 <<< ans: 0 <<< i: 1 c: 7 <<< ans: 0 <<< i: 2 c: 7 <<< ans: 0 <<< i: 3 c: 6 <<< ans: 0 arr3[6][7]: 1 <<< ans: 1 <<< i: 4 c: 6 <<< ans: 1 arr3[6][7]: 1 <<< ans: 2 <<< i: 5 c: 7 <<< ans: 2 arr3[7][6]: 2 <<< ans: 4 main <<< ans: 4 abbaab main <<< s ==>abbaab<== <<< i: 0 c: 0 <<< ans: 0 <<< i: 1 c: 1 <<< ans: 0 <<< i: 2 c: 1 <<< ans: 0 <<< i: 3 c: 0 <<< ans: 0 arr3[0][1]: 1 <<< ans: 1 <<< i: 4 c: 0 <<< ans: 1 arr3[0][1]: 1 <<< ans: 2 <<< i: 5 c: 1 <<< ans: 2 arr3[1][0]: 2 <<< ans: 4 main <<< ans: 4 akakak main <<< s ==>akakak<== <<< i: 0 c: 0 <<< ans: 0 <<< i: 1 c: 10 <<< ans: 0 <<< i: 2 c: 0 <<< ans: 0 <<< i: 3 c: 10 <<< ans: 0 <<< i: 4 c: 0 <<< ans: 0 arr3[0][10]: 1 <<< ans: 1 <<< i: 5 c: 10 <<< ans: 1 arr3[10][0]: 1 <<< ans: 2 main <<< ans: 2
These screen capture contains all the test cases provided by HackerRank plus a couple additional ones.
Since displaying large two dimensional arrays is harder to follow, such code has been commented out. This will become clearer as we look at the actual function of interest.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read the input string ****
String s = br.readLine().trim();
// **** close the buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< s ==>" + s + "<==");
// **** call the function of interest and display the result ****
System.out.println("main <<< ans: " + shortPalindrome(s));
}
This is the test code. The code is simple. We use a buffered reader to read the single input line that holds the lowercase string we will pass as an argument to the function of interest. The function is called and the result is displayed.
Remember to always (at least most of the times) follow the KISS principle when developing code. Your team and you will appreciate it when the code is debugged and enhanced.
// **** constants ****
static long MOD = 1000000007;
static int LETTER_COUNT = 26;
// static int LETTER_COUNT = 5; // for testing only
The first definition follows the problem requirements. The second is used to switch between lowercase vowels (5) and lowercase letters (26). This is done for testing purpose only.
/*
* Complete the 'shortPalindrome' function below.
*
* The function is expected to return an INTEGER.
* The function accepts STRING s as parameter.
*
* Execution: O(n * m) - Space: O(m + 2 * m^2)
*/
public static int shortPalindrome(String s) {
// **** sanity check(s) ****
if (s.length() <= 0) return s.length();
// **** initialization ****
long ans = 0;
long[] arr1 = new long[LETTER_COUNT];
long[][] arr2 = new long[LETTER_COUNT][LETTER_COUNT];
long[][] arr3 = new long[LETTER_COUNT][LETTER_COUNT];
// String vowels = "aeiou"; // for testing only
// **** traverse letters in the string - O(n) ****
for (int i = 0; i < s.length(); i++) {
// **** select current character ****
int c = s.charAt(i) - 'a';
// ???? ????
System.out.println("<<< i: " + i + " c: " + c);
// // ???? for testing only ????
// int c = vowels.indexOf(s.charAt(i));
// //???? ????
// System.out.println("<<< i: " + i + " c: " + vowels.charAt(c));
// **** update answer - O(m) ****
for (int j = 0; j < LETTER_COUNT; j++) {
// ???? ????
if (arr3[c][j] != 0)
System.out.println("<<< ans: " + ans + " arr3[" + c + "][" + j + "]: " + arr3[c][j]);
// **** ****
ans = (ans + arr3[c][j]) % MOD;
}
// ???? ????
System.out.println("<<< ans: " + ans);
// **** update contents of arrays arr3 and arr2 - O(m) ****
for (int j = 0; j < LETTER_COUNT; j++) {
arr3[j][c] = (arr3[j][c] + arr2[j][c]) % MOD;
arr2[j][c] = (arr2[j][c] + arr1[j]) % MOD;
}
// // ???? for testing only ????
// System.out.println("<<< arr3:");
// for (int k = 0; k < arr3.length; k++)
// System.out.println(Arrays.toString(arr3[k]));
// // ???? for testing only ????
// System.out.println("<<< arr2:");
// for (int k = 0; k < arr2.length; k++)
// System.out.println(Arrays.toString(arr2[k]));
// **** update contents of array arr1 ****
arr1[c] += 1;
// ???? for testing only ????
// System.out.println("<<< arr1:\n" + Arrays.toString(arr1));
}
// **** adjust and return answer ****
return (int)(ans % MOD);
}
We start the function of interest by performing a sanity check.
We then declare and initialize some variables. The `ans` will hold the number of 4-letter palindromes we find in the input string. The three arrays are used to keep track of the count of letters. In `arr1` we count the occurrence of a single character, in `arr2` the occurrence of two characters and in `arr3` the occurrence of three characters which may be candidates for a palindrome of four characters.
As we go over the code, please feel free to switch between the screen capture of the two test cases using vowels and the actual code. It is easier to start with a couple examples using fewer characters.
Note that some code is commented out and some other needs to be switched. I believe the changes are simple enough and must start at the top with the definition of the number of letters (LETTER_COUNT).
We enter a main loop used to traverse letters in the string from left to right. The 4-character palindromes must be constructed with characters that are in increasing positions in the string.
We start with a inner loop used to update our number of palindromes. As you can verify, the loop needs at least 4 characters from the string to start producing results.
We then need to update the arrays that are used to track the position of characters. This is the key of this approach. We update `arr3` and `arr2`.
Finally the count of single characters held in `arr1` is incremented.
When all is said and done, we need to return the integer value holding the number of palindromes.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).
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