// Valid Palindrome - https://leetcode.com/problems/valid-palindrome/

class Solution {

    // Time Complexity: O(n)
    // Space Complexity: O(n)
    // public boolean isPalindrome(String s) {
    //     s = s.toLowerCase();
    //     StringBuilder sb = new StringBuilder();

    //     for(int i = 0; i < s.length(); i++) {
    //         Character c = s.charAt(i);

    //         if(Character.isLetterOrDigit(c)) {
    //             sb.append(c);
    //         }
    //     }

    //     String toCheck = sb.toString();
    //     int i = 0, j = toCheck.length() - 1;

    //     while(i < j) {
    //         if(toCheck.charAt(i) != toCheck.charAt(j)) {
    //             return false;
    //         }
    //         i++;
    //         j--;
    //     }

    //     return true;
    // }


    // Time Complexity: O(n)
    // Space Complexity: O(n)
    // Similar to above but compact code
    // public boolean isPalindrome(String s) {
    //     StringBuilder sb = new StringBuilder();
    //     for(int i = 0; i < s.length(); i++) {
    //         Character c = s.charAt(i);

    //         if(Character.isLetterOrDigit(c)) {
    //             sb.append(Character.toLowerCase(c));
    //         }
    //     }

    //     return sb.toString().equals(sb.reverse().toString());
    // }

    // Two pointers optimized
    // Time Complexity: O(n)
    // Space Complexity: O(1)
    public boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;

        while (l < r) {
            while (l < r && !alphaNum(s.charAt(l))) {
                l++;
            }
            while (r > l && !alphaNum(s.charAt(r))) {
                r--;
            }
            if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) {
                return false;
            }
            l++; r--;
        }
        return true;
    }

    public boolean alphaNum(char c) {
        return (c >= 'A' && c <= 'Z' ||
                c >= 'a' && c <= 'z' ||
                c >= '0' && c <= '9');
    }
}