3. Palindrome Sentence.md

Difficulty	Source	Tags
Easy	160 Days of Problem Solving (BONUS PROBLEMS 🎁)	two-pointer-algorithm String Palindrome

🚀 3. Palindrome Sentence 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description:

Given a single string s, check if it is a palindrome sentence or not. A palindrome sentence is a sequence of characters that reads the same backward as forward after:

• Converting all uppercase letters to lowercase.
• Removing all non-alphanumeric characters.

🔍 Example Walkthrough:

Input:

s = "Too hot to hoot"

Output:

true

Explanation:
If we remove all non-alphanumeric characters and convert all uppercase letters to lowercase, the string becomes “toohottohoot”, which is a palindrome.

Input:

s = "Abc 012..## 10cbA"

Output:

true

Explanation:
After processing the string, it becomes "abc01210cba", which is a palindrome.

Input:

s = "ABC $. def01ASDF"

Output:

false

Explanation:
The processed string becomes "abcdef01asdf", which is not a palindrome.

Constraints:

• 1 ≤ s.size() ≤ 10^6

🎯 My Approach:

Step-by-Step:

1. Pointer Initialization:
   Start by initializing two pointers, i at the start of the string and j at the end of the string.

2. Skip Non-Alphanumeric Characters:
   Move the pointers i and j towards each other. If s[i] is not alphanumeric, increment i. Similarly, if s[j] is not alphanumeric, decrement j.

3. Check for Matching Characters:
   Once valid characters are found at both pointers, convert them to lowercase and compare:

   • If they are not equal, return false as it is not a palindrome.
   • Otherwise, move both pointers towards the center (increment i and decrement j).

4. End Condition:
   If the entire string is processed without mismatches, return true.

🕒 Time and Auxiliary Space Complexity:

• Time Complexity:
  The algorithm performs a linear scan of the string with two pointers moving from the ends towards the center, which takes O(n) time, where n is the length of the string.

• Auxiliary Space Complexity:
  The space complexity is O(1) as we are only using a few integer variables and no additional space proportional to the input size.

📝 Solution Code

Code (Cpp)

class Solution {
public:
    bool sentencePalindrome(string &s) {
        int i = 0, j = s.length() - 1;
        
        while (i < j) {
            if (!isalnum(s[i])) {
                i++;  
            } else if (!isalnum(s[j])) {
                j--;
            } else {
                if (tolower(s[i]) != tolower(s[j])) {
                    return false;  
                }
                i++;
                j--;
            }
        }
        
        return true;
    }
};

Code (Java)

class Solution {
    public boolean sentencePalindrome(String s) {
        int i = 0, j = s.length() - 1;

        while (i < j) {
            if (!Character.isLetterOrDigit(s.charAt(i))) {
                i++;
            } else if (!Character.isLetterOrDigit(s.charAt(j))) {
                j--;
            } else {
                if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
                    return false;
                }
                i++;
                j--;
            }
        }

        return true;
    }
}

Code (Python)

class Solution:
    def sentencePalindrome(self, s):
        i, j = 0, len(s) - 1
        
        while i < j:
            if not s[i].isalnum():
                i += 1
            elif not s[j].isalnum():
                j -= 1
            else:
                if s[i].lower() != s[j].lower():
                    return False
                i += 1
                j -= 1
        
        return True

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count