# LeetCode #125: Valid Palindrome (Solution in Python & Explanation)

In this article, I will be explaining how to solve the Valid Palindrome problem on LeetCode. This is an Easy-level problem.

## The Problem

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string `s`, return `true` if it is a palindrome, or `false` otherwise.

Example 1:

```Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.```

Example 2:

```Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.```

Example 3:

```Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.```

## Solution

Alphanumeric characters are the lowercase letters a-z, capital letters A-Z, and integers 0-9.

So, to solve this, we first want to remove all non-alphanumeric characters, including spaces, punctuation, etc., from the input string. Then, we need to check the new string to see if it’s a palindrome. We have two ways we can do this.

#### Solution #1

For this solution, we create a new string which contains all of the alphanumeric characters from the input string (lowercased). Then, we compare this new string to its reversed version. If they are the same, the function returns true. If not, it returns false.

In order to create the new string, we loop through the characters in the original input string and, if the character is alphanumeric, we append it to the new string.

Finally, we can check if the string (without any special characters or spaces) is a palindrome by using a boolean expression to equate it to its reverse. We can get the reverse of a string by using str[::-1]

```def isPalindrome(self, s: str) -> bool:
newStr = ""

for char in s:
if char.isalnum():
newStr += c.lower()
return newStr == newStr[::-1]```

This solution has a time complexity of O(n) because we have to loop through the string to remove non-alphanumeric characters. It also has a space complexity of O(n) because we are creating another string, which could be at most the size of the input string.

#### Solution #2

For this solution, we will create pointers to the beginning and end of the array which will make sure that the two sides have the same characters in the same order.

First, create two pointersâ€” one which points to the beginning of the string and the other which points to the end. The two pointers will move inwards, checking each character until the reach the middle or overlap with each other.

As the pointers loop through the characters, they will skip any characters that are not alphanumeric. To do this, we use while loops that will continue to run until the character at the `left`/`right` index is alphanumeric. We also add a check to make sure that the left/right index is in bounds by checking `left < right `/ `right > left`

We must make sure to compare the lowercase versions of the characters to each other. If any character at the left pointer does not match the corresponding character at the right pointer, then we know that itâ€™s not a palindrome and can return False. If the entire loop finishes then that must mean the string is a palindrome and we can return True.

```def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1

while left < right:
while left < right and not s[left].isalnum():
left +=1
while right > left and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left, right = left + 1, right - 1
return True```

The time complexity for this solution is O(n) because you are still looping through the entire string. The space complexity is O(1) because you are not making a new string.

# LeetCode #242: Valid Anagrams (Solution in Python & Explanation)

## The Problem

Given two strings `s` and `t`, return `true` if `t` is an anagram of `s`, and `false` otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

```Input: s = "anagram", t = "nagaram"
Output: true```

Example 2:

```Input: s = "rat", t = "car"
Output: false```

## Solution

We know that the two strings are anagrams if:

1. They have the same length
2. They have the same characters and the same quantity of each character

So, if we can verify that the strings pass these two criteria, we can verify that they are valid anagrams.

We can check if they are the same length by simply using `len`:

`len(s) == len(t)   # boolean expression`

But how can we check if they have the same characters and the same quantity of each character? We can use hash maps. For each string, we can create a hash map that includes every unique character in the string and its frequency in the string.

For example, this would be the hash map of the string `s`, which has a value of `"anagram"`:

```s = "anagram"
countS = {"a": 3, "n": 1, "g": 1, "m": 1}```

Once, we have created the hash maps, we can check if they are equivalent by using a boolean expression:

`countS == countT`

So, let’s put it all together. These are all the steps we have to take:

1. We check if the strings are not the same length. If they’re not, we can immediately return False without doing any other code.
2. We create empty hash maps for the two strings `s` and `t`.
3. We loop through each character in s and t and add them to the hash maps. If the character does not exist in the hash map, a new key for the character is added and the value is initialized to 0 (then we add 1). If a key for the character does exist in the hash map, we add 1 to the value.
4. We check if the two hash maps are equivalent. If they are, we return True. If they are not, we return False.

This is the final code.

```   def isAnagram(self, s: str, t: str) -> bool:
# Step 1: check if same length
if len(s) != len(t):
return False

# Step 2: create hash maps
countS = {}
countT = {}

# Step 3: loop through characters to add to hash map
for i in range(len(s)):
countS[s[i]] = 1 + countS.get(s[i], 0)
countT[t[i]] = 1 + countT.get(t[i], 0)

# Step 4: check if hash maps are equivalent
if (countS == countT):
return True
else:
return False```

This solution has a time complexity of O(s + t) or simply O(n) because we have to iterate through each of the strings. The space complexity is also O(s + t) because we are building hash maps that are the sizes of arrays s and t.

There is another solution that is much more simple, but less efficient. We can sort both of the strings and see if the sorted versions are equivalent. This works because, if they are anagrams, then they will have the same sorted value.

```def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)```

A good sorting algorithm can sort an array of characters in O(n * log(n)) time. The space complexity could be either O(1) or O(n)

# LeetCode: Two Sum (Solution in Python & Explanation)

In this article, I will be explaining how to solve the Two Sum problem on LeetCode. This is an Easy-level question for Arrays.

## The Problem

Given an array of integers `nums` and an integer `target`, return indices of the two numbers such that they add up to `target`.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

```Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].```

Example 2:

```Input: nums = [3,2,4], target = 6
Output: [1,2]```

Example 3:

```Input: nums = [3,3], target = 6
Output: [0,1]```

## The Solution

The most straightforward way to solve this problem is to check every combination of two values in the array and see if they can sum up to the `target` value. To do this, we would iterate through the entire array and for each item we would iterate through the array a second time to check the sums of the current array item with every other item in the array and see if they are the target. The (worst-case) runtime for this solution method is not very efficient: O(n`2)`.

There is a better solution that only requires us to loop through the array once. Basically, if we could loop through the array and, for each array item, check if the number that adds with that value to get the target exists in the array using an operation that doesn’t have O(n) time complexity, then we could make our program much faster. We can do this by using a hash map.

We create a hash map that will store array items as keys and their indexes in the array as values (`{array_value: array_index}`)

We use the enumerate function to get the index of the current item as we loop through the array. For each array item, we compute the difference `diff` between the target value and the item’s value. Since `target - n = diff`, that means `diff + n = target`. If this difference diff is in the hash map, then that means that the value has already been seen in the array. Thus, we’ve found the . If the difference is not in the array, then we add the current array item and its index to the hash map then move to the next array item.

```def twoSum(self, nums: List[int], target: int) -> List[int]:
hm = {}
for i, n in enumerate(nums):
diff = target - n
if diff in hm:
return [hm[diff], i]
hm[n] = i```

This solution has a time complexity of O(n) because we only have to loop through the `nums` array once and the lookup and insert operations into the hash map have a runtime of O(1). Although, we do have to use extra memory to create the hash map. The memory complexity is O(n) because we could potentially add every value to the hash map.

# LeetCode: Contains Duplicates (Solution in Python & Explanation)

In this article, I will be explaining how to solve the Contain Duplicates problem on LeetCode. This is an Easy-level question for Arrays.

## The Problem

Given an integer array `nums`, return `true` if any value appears at least twice in the array, and return `false` if every element is distinct.

Example 1:

```Input: nums = [1,2,3,1]
Output: true```

Example 2:

```Input: nums = [1,2,3,4]
Output: false```

Example 3:

```Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true```

## Solution

This problem requires that we loop through the array. We may not have to loop through the entire array depending on when / if we find the first duplicate.

As we loop through the array, we check each array item to see if we’ve seen it before. How can we check if we’ve seen a value in the array before? The naive method would be to do a second loop through the array for each. The program will have a complexity of O(n2) because you are looping through each array element and then, within that loop, you are looping through each array element again.

```def containsDuplicate(self, nums: List[int]) -> bool:
dups = set()
for n in nums:
for s in nums:
if n == s:
return True
return False```

This solution is slow and we can solve this problem in a more efficient way.

As we loop through the array, we can keep track of the values that we’ve seen thus far. Then, as we continue looping through and checking new values, we can check if they are already in the set of values that we’ve seen before. How can we keep track of the values that we’ve seen? We can use a hash set. This solution takes O(n) time because we are only looping through the array once instead of twice.

```def containsDuplicate(self, nums: List[int]) -> bool:
dups = set()
for n in nums:
if n in dups:
return True
```def containsDuplicate(self, nums: List[int]) -> bool: