---

Problem: Valid Palindrome

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<sup>5</sup>

• s consists only of printable ASCII characters.

---

Solution 1

class Solution {
    public boolean isPalindrome(String s) {
        int start = 0;
        int end = s.length() - 1;

        while (start < end) {
            if (!Character.isLetterOrDigit(s.charAt(start))) {
                start++;
                continue;
            }

            if (!Character.isLetterOrDigit(s.charAt(end))) {
                end--;
                continue;
            }

            if (Character.toLowerCase(s.charAt(start)) != Character.toLowerCase(s.charAt(end))) {
                return false;
            }

            start++;
            end--;
        }

        return true;
    }
}

1. Initialization:

   • start and end are initialized to the start and end indices of the input string s, respectively. These pointers will be used to compare characters from both ends of the string.

2. Main Loop:

   • The while loop continues as long as start is less than end, ensuring that the pointers do not cross each other.

3. Character Validation:

   • The first if statement checks if the character at the start position is not a letter or digit using the Character.isLetterOrDigit() method. If true, it means we've encountered a non-alphanumeric character from the left end. So, we increment the start pointer and continue to the next iteration.

   • Similarly, the second if statement checks the character at the end position. If it's not a letter or digit, the end pointer is decremented and we continue to the next iteration.

4. Palindrome Check:

   • After skipping non-alphanumeric characters from both ends, we compare the characters at the start and end positions. We use Character.toLowerCase() to convert characters to lowercase before comparing, ensuring a case-insensitive check.

   • If the characters are not equal, the string is not a palindrome, and we return false.

5. End of Loop:

   • If the characters matched for all valid alphanumeric characters in the string, the while loop completes, and the method returns true, indicating that the input string is a palindrome.

Complexities

Time Complexity: O(n)

The time complexity of an algorithm represents the amount of time taken by an algorithm to run as a function of the length of the input.

1. Iterative Traversal:

   • The code uses a while loop that traverses the string from both ends (from start to end). This means the loop will run for at most half the length of the string, since you're comparing characters from both ends simultaneously.

   • Thus, the time complexity of the while loop is O(n/2), which simplifies to O(n), where n is the length of the input string s.

2. Character Comparisons and Checks:

   • Inside the loop, individual character comparisons and checks (like Character.isLetterOrDigit() and Character.toLowerCase()) are constant-time operations.

Combining these factors, the overall time complexity of the isPalindrome method is O(n).

Space Complexity: O(1)

The space complexity of an algorithm represents the amount of memory space required by an algorithm to run as a function of the length of the input.

1. Character Variables:

   • The space usage in the code is primarily for the two integer variables (start and end), which require constant space regardless of the input size.

2. No Extra Data Structures:

   • The method does not use any additional data structures or arrays based on the input size. All operations are done in-place on the input string s

Thus, the space complexity of the isPalindrome method is O(1) or constant space, since the space used is not dependent on the size of the input string.

---

Solution 2

class Solution {
    public boolean isPalindrome(String s) {
        int start = 0;
        int end = s.length() - 1;

        char left, right;

        while (start < end) {
            left = s.charAt(start);
            right = s.charAt(end);

            if (left >= 65 && left <= 90) {
                left += 32;
            }

            if (right >= 65 && right <= 90) {
                right += 32;
            }

            if (!((left >= 48 && left <= 57) || (left >= 97 && left <= 122))){
                start++;
                continue;
            }

             if (!((right >= 48 && right <= 57) || (right >= 97 && right <= 122 ))) {
                end--;
                continue;
            }

            if (left != right) {
                return false;
            }

            start++; end--;
        }

        return true;
    }
}

1. Initialization:

   • start and end are initialized to the start and end indices of the input string s, respectively. These pointers will be used to compare characters from both ends of the string.

   • left and right are variables to temporarily hold the characters at positions start and end, respectively.

2. Main Loop:

   • The while loop continues as long as start is less than end, ensuring that the pointers do not cross each other.

3. Character Conversions and Checks:

   • The characters at the current start and end positions are retrieved using s.charAt(start) and s.charAt(end), respectively, and stored in left and right.

   • The next two if statements are for converting uppercase letters to lowercase by adding 32 to their ASCII values (since the ASCII values of uppercase and lowercase alphabets differ by 32). This ensures case-insensitive comparison later on. (Reference: ASCII Table)

   • The following two if statements check if the characters left and right are not alphanumeric:

     • For left: If it's not a digit (ASCII range 48-57) and not a lowercase letter (ASCII range 97-122), we increment start and continue to the next iteration.

     • For right: Similarly, if it's not a digit or lowercase letter, we decrement end and continue to the next iteration.

4. Palindrome Check:

   • After ensuring that left and right are valid alphanumeric characters, they are compared. If they're not equal, the method returns false, indicating that the string is not a palindrome.

5. End of Loop:

   • If the characters matched for all valid alphanumeric characters in the string, the while loop completes, and the method returns true, indicating that the input string is a palindrome.

Complexities

Time Complexity: O(n)

1. Iterative Traversal:

   • The code uses a while loop that traverses the string from both ends (from start to end). This means the loop will run for at most half the length of the string, since you're comparing characters from both ends simultaneously.

   • Thus, the time complexity of the while loop is O(n/2), which simplifies to O(n), where n is the length of the input string s.

2. Character Comparisons and Checks:

   • Inside the loop, individual character comparisons and checks (like the ones for alphanumeric characters and case conversion) are constant-time operations. Therefore, their contribution to the overall time complexity is also O(n).

Combining these factors, the overall time complexity of the isPalindrome method is O(n).

Space Complexity: O(1)

1. Character Variables:

   • The space usage in the code is primarily for the two integer variables (start and end), which require constant space regardless of the input size.

   • Additionally, the method uses two character variables (left and right) for temporary storage during comparisons. These are also constant space.

2. No Extra Data Structures:

   • The method does not use any additional data structures or arrays based on the input size. All operations are done in-place on the input string s.

Thus, the space complexity of the isPalindrome method is O(1) or constant space, since the space used is not dependent on the size of the input string.