## HackerRank: Palindrome Index

To read the full prompt, navigate to HackerRank Palindrome Index Question.

The core of this question is determining whether or not an input string is a palindrome in its current orientation or determining the index of a character that could be removed to make the input string a palindrome.

Here are some examples that Hackerrank provides:

`Test Case 1: "aaab"Removing 'b' at index 3 results in a palindrome, so we print on a new line.`

Test Case 2: “baa”
Removing ‘b’ at index 0 results in a palindrome, so we print on a new line.

`Test Case 3: "aaa"This string is already a palindrome, so we print -1; however, 0, 1, and 2 are also all acceptable answers, as the string will still be a palindrome if any one of the characters at those indices are removed.`

The naive implementation is to remove every single character while constructing a new string every iteration and checking whether the new string is a palindrome. This implementation is slow and we can do better.

For a string to be a palindrome, we know that the string must be reversible. In other words, every character leading up to the length of the string divided two must have a corresponding character on the opposite side of the string. We don’t have to worry about when an input string’s length is odd because the middle character reversed would always be itself. With this knowledge, we know we can solve this problem iterating through the first half of characters and compare them to the second half of characters. As soon as we hit a pair of characters not equal, we know that one of the two characters can be removed from the original input string to form a palindrome. We only have to check that one of the characters is a palindrome due to the requirements dictating that there will always be a valid solution.

In this instance, checking if a string is a palindrome is a little more difficult than usual because we must take into account the index to exclude. To do this, we iterate through the length of the string divided two and compare the first half of characters to the second half of characters. The character that needs to be excluded is just skipped over. Alternatively, one could simply copy the string and then check the reverse order property but that would be a waste of memory.

Here is my Java solution to this problem:

```public class Solution {
/**
* Determines if a string is a palinderome while excluding a character denoted  index. This prevents
us from having to make another string which is the exact same as the original string
excluding the 'indexToExclude' argument.
*
*
**/
private static boolean isPalindrome(String possiblePalindrome, int indexToExclude){
int halfOfStringLength = possiblePalindrome.length() / 2;
for(int i = 0; i < halfOfStringLength; i++){
int firstHalfIndex = i;
int secondHalfIndex = possiblePalindrome.length() - i - 1;

if(firstHalfIndex >= indexToExclude){
firstHalfIndex += 1;
}
if(secondHalfIndex <= indexToExclude){
secondHalfIndex -= 1;
}
if(possiblePalindrome.charAt(firstHalfIndex) != possiblePalindrome.charAt(secondHalfIndex)){
return false;
}
}
return true;
}
/**
*@return the index of the character that needs to be removed to make a palindrome. Note that if the string is already in palindrome orientation, then -1 will be returned.
*
**/
private static int getPalindromeIndex(String possiblePalindrome){
int halfOfNextLineLength = possiblePalindrome.length() / 2;
for(int j = 0; j < halfOfNextLineLength; j++){
int secondHalfIndex = possiblePalindrome.length() -  j - 1;
if(possiblePalindrome.charAt(j) != possiblePalindrome.charAt(secondHalfIndex)){
if(isPalindrome(possiblePalindrome, j)){
return j;
} else {
return secondHalfIndex;
}
}
}
return -1;
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String numberOfInputs = scanner.nextLine();

for(int i = 0; i < Integer.valueOf(numberOfInputs); i++){
String next = scanner.nextLine();
System.out.println(getPalindromeIndex(next));
}
scanner.close();
}
}```

Do you see a faster way to do this? Comment below!

## LeetCode: 2. Add Two Numbers

LeetCode Prompt:

```/** This prompt belongs to LeetCode **/

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8```

You really have to read this prompt a few times before letting it sink in. I think the most overlooked detail is that “The digits are stored in reverse order….” This is an incredibly important detail because it makes the algorithm a lot more simple; we don’t have to do any backwards carrying. In other words, 2 -> 4 -> 3 really represents the number ‘342’ and so forth for every other ListNode.

Here is the code I came up with:

```/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode tmpL1 = l1;
ListNode tmpL2 = l2;
int carryOver = 0;
while(tmpL1 != null && tmpL2 != null){
tmpL1.val = tmpL1.val + tmpL2.val + carryOver;
if(tmpL1.val >= 10){
carryOver = 1;
tmpL1.val -= 10;
if(tmpL1.next == null && tmpL2.next == null){
tmpL1.next = new ListNode(carryOver);
return l1;
}
} else {
carryOver = 0;
}

if(tmpL1.next == null && tmpL2.next != null){
tmpL1.next = new ListNode(0);
}
if(tmpL1.next != null && tmpL2.next == null){
tmpL2.next = new ListNode(0);
}

tmpL1 = tmpL1.next;
tmpL2 = tmpL2.next;

}
return l1;
}
}```

This code is simply iterating over every entry in the first and second ListNode and adding the values together. Following this, the algorithm checks if the summation is greater than or equal to 10 which denotes that we need to carry to the right. Since we only have to deal with digits, the max summation can only total 18 which means that the max carry over is 1. We have to do some conditional checking regarding null pointers due to uneven sizes of the ListNode.

See any improvements to make this faster? Comment below!

## Iterative Preorder Binary Tree Traversal

The typical definition of a preorder binary tree traversal is that you will first visit the top node, all nodes left of the tree, and then work your way back up the tree visiting the right nodes.

The typical recursive preorder binary tree traversal is this:

```private void preorderTraversal(IntegerNode integerNode) {
if (integerNode == null) {
return;
}
System.out.print(integerNode.value + "\t");
preorderTraversal(integerNode.left);
preorderTraversal(integerNode.right);
}```

Notice how we first check the current node, recurse through the left nodes, and then work our way back up the tree visiting the right nodes.

Whenever you have to rewrite recursion to iteration, you should be thinking “Stack”. This is because each recursive function call is really just an element that is pushed onto the stack behind the scenes.

Here is this same algorithm written to use iteration:

```private void iterativePreorderTraversal(IntegerNode integerNode){
Stack<IntegerNode> integerNodeStack = new Stack<>();
integerNodeStack.push(integerNode);

while(!integerNodeStack.isEmpty()){
IntegerNode integerNodeIterator = integerNodeStack.pop();

System.out.print(integerNodeIterator.value + "\t");

if(integerNodeIterator.right != null){
integerNodeStack.push(integerNodeIterator.right);
}
if(integerNodeIterator.left != null){
integerNodeStack.push(integerNodeIterator.left);
}

}
}```

We can think logically about this algorithm and trace through it to help us achieve a better understanding. First, the first node that will be popped off the stack will be the top of the binary tree (in this case the integerNode method argument). Second, we will keep adding the right and left nodes provided either of them are not null. The most important part to notice at this stage is that all left elements will be popped before any right elements because the stack data-structure guarantees the LIFO (last in first out) property. In our case, the current iteration will always have the left node being pushed into the stack after the right node, provided the left node is not null. After we have exhausted all the left nodes, we will start climbing back up the tree.

Feel free to leave any questions or comments below.