Validate Palindrome

Given a string str, can you write a method that will return True if is a palindrome and False if it is not? If you'll recall, a palindrome is defined as "a word, phrase, or sequence that reads the same backward as forward". For now, assume that we will not have input strings that contain special characters or spaces, so the following examples hold:

let str = 'thisisnotapalindrome';
isPalindrome(str);
// false

str = 'racecar';
isPalindrome(str);
// true

String str = "thisisnotapalindrome";
boolean isPalindrome = isPalindrome(str);
// false

str = "racecar";
isPalindrome = isPalindrome(str);
// true

str = 'thisisnotapalindrome'
is_palindrome = is_palindrome(str)
# False

str = 'racecar'
is_palindrome = is_palindrome(str)
# True

std::string str = "thisisnotapalindrome";
bool isPalindrome = isPalindrome(str);
// false

str = "racecar";
isPalindrome = isPalindrome(str);
// true

For an extra challenge, try to ignore non-alphanumerical characters. The final solution that we present will handle all edge cases.

Constraints

• Length of the given string <= 100000
• The string will consist of ASCII characters (some or all)
• Expected time complexity : O(n)
• Expected space complexity : O(1)

A string is defined as a palindrome if the reversal of the string is equal to the original string.

For example, “toot” is a palindrome, but “boot” is not.

This is a classic question, and there are multiple ways to solve this. For the sake of learning, let's cover all of them!

Using built-in methods

This would probably be invalid in an actual interview, but you can rely on the built-in String method to accomplish a quick reversal. In Javascript, you can simply call reverse() and in Python, you can call [::-1] You can then compare the reversed string to the original:

```js
function isPalindrome(str) {
	// Calling reverse function
	const reversed = str.split('').reverse().join('');

	// Checking if both strings are equal or not
	if (str == reversed) {
		return true;
	}
	return false;
}

console.log(isPalindrome('racecar'));
```
```java
boolean isPalindrome(String s) {
    // Calling reverse function
    String reversed = new StringBuilder(s).reverse().toString();

    // Checking if both strings are equal or not
    if (s.equals(reversed)) {
        return true;
    }
    return false;
}

System.out.println(isPalindrome("racecar"));
```
```python
def isPalindrome(s):
    # Calling reverse function
    reversed = s[::-1]

    # Checking if both strings are equal or not
    if s == reversed:
        return True
    return False

print(isPalindrome("racecar"))
```
```cpp
#include <algorithm>
#include <iostream>

bool isPalindrome(std::string s) {
    // Calling reverse function
    std::string reversed(s);
    std::reverse(reversed.begin(), reversed.end());

    // Checking if both strings are equal or not
    return s == reversed;
}

int main() {
    std::cout << std::boolalpha << isPalindrome("racecar") << std::endl;
}
```
```csharp
using System;

bool IsPalindrome(string s)
{
    // Calling reverse function
    char[] arr = s.ToCharArray();
    Array.Reverse(arr);
    string reversed = new string(arr);

    // Checking if both strings are equal or not
    if (s == reversed)
    {
        return true;
    }
    return false;
}

Console.WriteLine(IsPalindrome("racecar"));
```
```go
package main

import (
	"fmt"
	"strings"
)

func isPalindrome(s string) bool {
	// Calling reverse function
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	reversed := string(runes)

	// Checking if both strings are equal or not
	if s == reversed {
		return true
	}
	return false
}

func main() {
	fmt.Println(isPalindrome("racecar"))
}
```

What's the order of successfully finding out if a string is a palindrome?

What will the following pseudocode do to an input string?

def reverse_str(str):
  start = 0
  end = len(str)-1
  str_copy = [letter for letter in str]
  while start < end:
    temp = str_copy[start]
    str_copy[start] = str_copy[end]
    str_copy[end] = temp
    start += 1
    end -= 1
  return "".join(str_copy)

public static String reverseStr(String str) {
    int start = 0;
    int end = str.length() - 1;
    char[] strCopy = str.toCharArray();
    while (start < end) {
        char temp = strCopy[start];
        strCopy[start] = strCopy[end];
        strCopy[end] = temp;
        start++;
        end--;
    }
    return new String(strCopy);
}

function reverseStr(str) {
    let start = 0;
    let end = str.length - 1;
    let strCopy = Array.from(str);
    while (start < end) {
        let temp = strCopy[start];
        strCopy[start] = strCopy[end];
        strCopy[end] = temp;
        start++;
        end--;
    }
    return strCopy.join('');
}

#include <algorithm>
std::string reverseStr(std::string str) {
    int start = 0;
    int end = str.length() - 1;
    while (start < end) {
        std::swap(str[start], str[end]);
        start++;
        end--;
    }
    return str;
}

public static string ReverseStr(string str)
{
    int start = 0;
    int end = str.Length - 1;
    char[] strCopy = str.ToCharArray();
    while (start < end)
    {
        char temp = strCopy[start];
        strCopy[start] = strCopy[end];
        strCopy[end] = temp;
        start++;
        end--;
    }
    return new string(strCopy);
}

func reverseStr(str string) string {
    strCopy := []rune(str)
    start := 0
    end := len(str) - 1
    for start < end {
        strCopy[start], strCopy[end] = strCopy[end], strCopy[start]
        start++
        end--
    }
    return string(strCopy)
}

With a while loop:

We can cut down on the number of operations by recognizing that we don't need to do len(str)-1 iterations. Instead of using just one pointer that simply iterates through the string from its end, why not use two?

```js
function isPalindrome(str) {
	let left = 0;
	let right = str.length - 1;
	let leftChar;
	let rightChar;

	while (left < right) {
		leftChar = str.charAt(left);
		rightChar = str.charAt(right);

		if (leftChar == rightChar) {
			left++;
			right--;
		} else {
			return false;
		}
	}

	return true;
}

console.log(isPalindrome('racecar'));
```
```java
public static boolean isPalindrome(String str) {
    int left = 0;
    int right = str.length() - 1;
    char leftChar;
    char rightChar;

    while (left < right) {
        leftChar = str.charAt(left);
        rightChar = str.charAt(right);

        if (leftChar == rightChar) {
            left++;
            right--;
        } else {
            return false;
        }
    }

    return true;
}

public static void main(String[] args) {
    System.out.println(isPalindrome("racecar"));
}
```
```python
def is_palindrome(str):
    left = 0
    right = len(str) - 1
    while left < right:
        if str[left] != str[right]:
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome('racecar'))
```
```csharp
public static bool IsPalindrome(string s)
{
    int left = 0;
    int right = s.Length - 1;
    while (left < right) 
    {
        if (s[left] != s[right]) 
        {
            return false;
        }
        left += 1;
        right -= 1;
    }
    return true;
}

public static void Main(string[] args)
{
    Console.WriteLine(IsPalindrome("racecar"));
}
```
```cpp
#include <iostream>
#include <string>

bool isPalindrome(std::string s) {
    int left = 0;
    int right = s.length() - 1;
    while(left < right)
    {
        if(s[left] != s[right])
            return false;
        left++;
        right--;
    }
    return true;
}

int main() {
    std::cout << isPalindrome("racecar") << std::endl;
    return 0;
}
```
```go
package main

import (
	"fmt"
)

func isPalindrome(s string) bool {
	left := 0
	right := len(s) - 1
	for left < right {
		if s[left] != s[right] {
			return false
		}
		left++
		right--
	}
	return true
}

func main() {
	fmt.Println(isPalindrome("racecar"))
}
```

What we're doing above is specifying two pointers, start and end. start points to the beginning of the string, and end is a pointer to the last character. Taking the example input racecar, as we run through it, these are the comparisons we'll see:

```
racecar
^     ^
racecar
 ^   ^
racecar
  ^ ^
racecar
   ^
True
```

What is the run time of the following code?

def reverse_str(str):
  start = 0
  end = len(str)-1
  str_copy = [letter for letter in str]
  while start < end:
    temp = str_copy[start]
    str_copy[start] = str_copy[end]
    str_copy[end] = temp
    start += 1
    end -= 1
  return "".join(str_copy)

Complexity of Final Solution

Let n be the length of the string. We iterate n/2 times until the left pointer is greater than the right pointer for linear O(n) time complexity, and we use a constant O(1) space for the 2 pointers.

One Pager Cheat Sheet

• You can write a method using O(n) time and O(1) space complexity to check if a given string of length 100000 or less is a palindrome, taking into account non-alphanumerical characters.
• The given string is a palindrome if it reads the same forwards as it does backwards.
• With built-in methods, you can easily reverse() or [::-1] a String and then compare it to the original to check if it is a palindrome.
• By utilizing two variables, low and high, to represent the starting and ending indices of a string to be checked, and using a while loop to compare characters at these indices, we can determine if a string is a palindrome or not.
• The code reverses a string by looping over the characters, swapping the characters and keeping track of the start and end indexes using a temp variable, and then joining the characters of the str_copy list to return the reversed string.
• We can reduce complexity by using two pointers instead of one and only have to do len(str)/2 iterations of the while loop in order to validate if a string is a palindrome.
• Comparing characters of a string with two pointers, start pointing to the beginning and end pointing to the last character, the example input racecar shows us the initial comparisons.
• The runtime of the code is O(n), with O(1) space complexity, where n is the length of the string, since it iterates linearly with a constant space overhead.