Hello from the other side!!!
That was my best Adele imitation. I tried. I couldn’t find a more befitting reference for our love story.
Disclaimer: I didn’t come up with this problem. Thanks to a friend that will not be named, I had to solve this recently and thought to share.
A love letter from a shy lover
Now that I think about it, in a previous life, I wrote a love letter, shredded it to pieces, and then sent it out. I wasn’t shy, it was just a fun exercise for someone who loved to solve puzzles.
Unlike me, the letter we will be encoding today is not shredded into pieces for us to couple, however, we have to hide the true message because the sender is shy. We have just a two rules to encode this letter,
All the words in the letter should be converted to palindromes.
In order to arrive at the encoded letter, a character can only be reduced i.e the letter “k” can be reduced to “a” while “a” cannot be increased to “k”. Each reduction is counted as ONE change.
We are required to return the number of changes - in an array - that matches the changes required to update the word at an index to a palindrome.
For example, “abc” requires two changes to arrive at the palindrome: “aba”. “c” => “b” => “a”. Similarly, “abb” will require a single change to arrive at the same palindrome.
Problems
What are your thoughts? Can you attempt to solve it? What algorithms come to mind?
The first challenge, and perhaps the only one is: "how do I manage the change count?” There are 25 characters in the English alphabet, how do I calculate the distance between any two characters? And in good time?!
Any ideas?
Solution
Note: A palindrome is a string that reads the same forward as it does backward. Mom, civic, abba, ma’am, level etc.
Let’s take a look at one of the example words: “abc”. How do we convert this to a palindrome? We consider the characters at both ends “a” and “c”. As per our limitation, we can only reduce characters, thus “c” has to be reduced to “a”. This results in two moves from “c” to “a”. We now have “aba” after reducing “c”. We have our palindrome. Yay! We’ve done it.
We can take a look at the second word: “abcd”. Not we, you. How many changes do you count? I hope you got it right!
Now that we can do it by hand, what algorithm comes to mind? Two pointer. Our algorithm becomes, for each word:
Declare high and low pointers to point to the first and last index of the word.
Compare the characters at the high and low pointers.
Optionally reduce the higher character.
Maintain a count of the number of changes needed to reduce a character.
Return the total number of changes
Code
const loveStory = (letters) => {
//store english characters and their positions
const chars = {
'a': 1,
'b': 2,
'c':3,
'd':4,
'e':5,
'f':6,
'g':7,
'h':8,
'i':9,
'j':10,
'k' :11,
'l' :12,
'm' :13,
'n' :14,
'o' :15,
'p' :16,
'q' :17,
'r':18,
's' :19,
't':20,
'u' :21,
'v' :22,
'w' :23,
'x' :24,
'y' :25,
'z' :26
}
const res = []
for(const letter in letters) {
const word = letters[letter]
let high = word.length - 1
let low = 0
let changes = 0
while(low < high) {
if(word[low] !== word[high]) {
if(chars[word[high]] > chars[word[low]]) {
changes += chars[word[high]] - chars[word[low]]
}else {
changes += chars[word[low]] - chars[word[high]]
}
}
high--
low++
}
res.push(changes)
changes = 0
}
return res
}
console.log(loveStory(["abcd", "kfa", "hffv",
"zycfjuvrhxf", "fdjsqlgmcux"]))
You may have noticed how I solved the challenge I mentioned at the start of this newsletter. To count the changes needed to reduce each character, I opted to create an object to store each character and their position in the english alphabet. With this object, you can calculate the distance between any two characters in constant time.
Conclusion
This was particularly fun to solve, for reasons I cannot explain but I do hope you enjoyed it and found it interesting as well.
As always, let me know if there’s anything you’d like me to cover in a future edition.
Cheers!