---
Difficulty: Easy
Source: 160 Days of Problem Solving (BONUS PROBLEMS 🎁)
Tags:
- two-pointer-algorithm
- String
- Palindrome
-
---
# 🚀 _3. Palindrome Sentence_ 🧠
The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/string-bonus-problems/problem/string-palindromic-ignoring-spaces4723)
## 💡 **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)
```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)
```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)
```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](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
---
📍Visitor Count
