Valid Palindrome

A palindrome is a word, phrase, or sequence of characters that reads the same backward as forward. For example, “racecar” is a palindrome because it is spelled the same way forwards and backwards.

A valid palindrome is a palindrome that also meets certain conditions. One common condition is that spaces and punctuation marks are ignored when determining if a sequence of characters is a palindrome. For example, the phrase “A man, a plan, a canal: Panama” is a valid palindrome because it reads the same way forwards and backwards when spaces and punctuation are ignored.

Another condition for a valid palindrome is that the characters must be in the same case, meaning either all uppercase or all lowercase. For example, the phrase “Racecar” would not be considered a valid palindrome because the first letter is uppercase while the rest are lowercase.

Checking if a sequence of characters is a valid palindrome is a common problem in computer science and can be solved using various algorithms. One approach is to compare the first and last characters of the sequence, then move inward until all characters have been compared. If at any point two characters do not match, the sequence is not a palindrome. If all characters match, the sequence is a palindrome.

Here are some examples of valid palindromes:

1. “A man, a plan, a canal: Panama” – This phrase reads the same way forwards and backwards when spaces and punctuation are ignored.
2. “Madam, in Eden I’m Adam” – This phrase reads the same way forwards and backwards when spaces and punctuation are ignored.
3. “Never odd or even” – This phrase reads the same way forwards and backwards when spaces and punctuation are ignored.
4. “Radar” – This word is a palindrome because it reads the same way forwards and backwards.
5. “Level” – This word is a palindrome because it reads the same way forwards and backwards.
6. “Deified” – This word is a palindrome because it reads the same way forwards and backwards.
7. “Was it a car or a cat I saw?” – This phrase reads the same way forwards and backwards when spaces and punctuation are ignored.

Note that in all of these examples, the characters are in the same case and spaces and punctuation are ignored when determining if the sequence is a palindrome.

Solutions for Valid Palindrome problem

Approach 1: Brute Force

The first approach is a brute force method that involves checking every pair of characters in the sequence to see if they match. To do this, we can use two nested loops. The outer loop iterates through each character in the sequence, and the inner loop compares the current character to every character in the sequence starting from the end.

function isPalindrome(sequence):
    n = length(sequence)
    for i from 0 to n-1:
        for j from n-1 down to 0:
            if sequence[i] != sequence[j]:
                return false
            i++
            j--
    return true

Time complexity: O(n^2) Space complexity: O(1) Code complexity: The code is easy to understand and implement, but it is inefficient.

Approach 2: Using a Stack

The second approach involves using a stack to compare the characters in the sequence. First, we push each character in the sequence onto a stack. Then, we pop each character off the stack and compare it to the corresponding character in the sequence. If all the characters match, the sequence is a palindrome.

function isPalindrome(sequence):
    stack = empty stack
    n = length(sequence)
    for i from 0 to n-1:
        stack.push(sequence[i])
    for i from 0 to n-1:
        if sequence[i] != stack.pop():
            return false
    return true

Time complexity: O(n) Space complexity: O(n) Code complexity: The code is slightly more complex than the brute force approach, but it is more efficient.

Approach 3: Using Two Pointers

The third approach involves using two pointers to compare the characters in the sequence. We use one pointer to point to the first character in the sequence and another pointer to point to the last character. We then compare the characters at each pointer and move the pointers inward until they meet in the middle of the sequence. If all the characters match, the sequence is a palindrome.

function isPalindrome(sequence):
    n = length(sequence)
    i = 0
    j = n-1
    while i < j:
        if sequence[i] != sequence[j]:
            return false
        i++
        j--
    return true

Time complexity: O(n) Space complexity: O(1) Code complexity: The code is slightly more complex than the stack approach, but it is more space-efficient.

Let’s compare each solution and see which one is better?

Approach 1: Brute Force The brute force approach for determining if a sequence is a valid palindrome involves checking every pair of characters in the sequence to see if they match. To do this, we use two nested loops. The outer loop iterates through each character in the sequence, and the inner loop compares the current character to every character in the sequence starting from the end. This approach is easy to understand and implement, but it has a time complexity of O(n^2), which makes it very inefficient for large sequences.

Approach 2: Using a Stack The stack approach involves using a stack data structure to compare the characters in the sequence. We first push each character in the sequence onto a stack. Then, we pop each character off the stack and compare it to the corresponding character in the sequence. If all the characters match, the sequence is a palindrome. This approach has a time complexity of O(n) and is more efficient than the brute force approach. However, it requires additional space for the stack, which has a space complexity of O(n).

Approach 3: Using Two Pointers The two-pointer approach involves using two pointers to compare the characters in the sequence. We use one pointer to point to the first character in the sequence and another pointer to point to the last character. We then compare the characters at each pointer and move the pointers inward until they meet in the middle of the sequence. If all the characters match, the sequence is a palindrome. This approach has a time complexity of O(n) and a space complexity of O(1), which makes it the most efficient and space-efficient solution. However, it is slightly more complex to implement than the stack approach.

For me two-pointer approach is the most efficient and space-efficient solution for the valid palindrome problem, followed by the stack approach. The brute force approach is the least efficient and should only be used for small sequences

Valid Palindrome Java Solution:

public boolean isPalindrome(String s) {
    s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) {
            return false;
        }
        i++;
        j--;
    }
    return true;
}

Valid Palindrome JavaScript Solution:

function isPalindrome(s) {
    s = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
    let i = 0, j = s.length - 1;
    while (i < j) {
        if (s[i] !== s[j]) {
            return false;
        }
        i++;
        j--;
    }
    return true;
}

Valid Palindrome Ruby Solution:

def is_palindrome(s)
    s = s.gsub(/[^a-zA-Z0-9]/, '').downcase
    i = 0
    j = s.length - 1
    while i < j
        if s[i] != s[j]
            return false
        end
        i += 1
        j -= 1
    end
    return true
end

Valid Palindrome Python Solution:

def is_palindrome(s):
    s = ''.join(filter(str.isalnum, s)).lower()
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

Explanation:

• First, we remove any non-alphanumeric characters from the sequence and convert all characters to lowercase.
• We then use two pointers, one at the beginning of the sequence and one at the end of the sequence.
• While the two pointers have not met in the middle of the sequence, we compare the characters at the two pointers. If they don’t match, the sequence is not a palindrome.
• If we reach the middle of the sequence and all characters have matched, the sequence is a palindrome.

The time complexity for this approach is O(n), where n is the length of the sequence, since we only need to iterate through the sequence once. The space complexity is O(1), since we are only using a constant amount of extra space to store the two pointers.

This approach is more efficient than the brute force approach, which has a time complexity of O(n^2), and is more space-efficient than the stack approach, which has a space complexity of O(n). Overall, the two-pointer approach is the most efficient and space-efficient solution for the valid palindrome problem.