1. Valid palindrome

Description

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.

Constraints:

• 1 <= s.length <= 2 * 10^5
• s consists only of printable ASCII characters.

Approach

• Take two pointer one from start and other from end if it is letter or digit continue else check if it is unequal in any case and return false

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;
 
        while(i < j) {
            Character start = s.charAt(i);
            Character end = s.charAt(j);
 
            if(!Character.isLetterOrDigit(start)) {
                i++;
                continue;
            }
 
            if(!Character.isLetterOrDigit(end)) {
                j--;
                continue;
            }
 
            if(Character.toLowerCase(start) != Character.toLowerCase(end)) return false;
 
            i++;
            j--;
        }
 
        return true;
    }
}

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        Map<Integer, Integer> freq = new HashMap<>();
 
        for (int i = 0; i < numbers.length; i++) {
            int diff = target - numbers[i];
            if (freq.containsKey(diff))
                return new int[] { freq.get(diff) + 1, i + 1 };
            freq.put(numbers[i], i);
        }
 
        return new int[] { 0, 0 };
    }
}

Approach 2 (Best space complexity)

• Create two pointers check if there sum equals target and break else increase/decrease the pointers

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
 
        while (i < j) {
            int start = numbers[i];
            int end = numbers[j];
 
            if (start + end == target)
                break;
 
            if (start + end < target)
                i++;
            else
                j--;
        }
 
        return new int[] { i + 1, j + 1 };
    }
}

class Solution {
    public boolean isPalindrome(int x) {
        int rev = 0;
        int tmp = x;
 
        while(tmp > 0) {
            rev = rev*10 + tmp%10;
            tmp /= 10;
        }
 
        if(rev == x) {
            return true;
        } else {
            return false;
        }
    }
}

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder str = new StringBuilder();
        for(char c: s.toCharArray()) {
            if(Character.isLetterOrDigit(c)) {
                str.append(Character.toLowerCase(c));
            }
        }
        return str.toString().equals(str.reverse().toString());
    }
}