Given a string, determine if it is a palindrome.

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward

**Example 1:**

Input:"madam racecar madam"Output:true

**Example 2:**

Input:"abcbx"Output:false

Your algorithm should run in **O(n)** time and use **O(1)** extra space.

The problem requires us to determine if a given string is a palindrome. A palindrome is a sequence of characters that reads the same backward as forward.

**Input:** A string `s`

.

**Output:** A boolean value `true`

if the string is a palindrome, otherwise `false`

.

**Constraints:**

- The algorithm should run in O(n) time.
- The algorithm should use O(1) extra space.

**Example:**

Input:"madam racecar madam"Output:true

Input:"abcbx"Output:false

The core challenge is to check if the string reads the same backward as forward. This is significant in various applications such as text processing, DNA sequence analysis, and more. A common pitfall is to overlook the need for an efficient solution that runs in linear time and uses constant space.

To solve this problem, we can use a two-pointer technique:

- Initialize one pointer at the beginning of the string and another at the end.
- Compare the characters at these pointers.
- If they are equal, move the pointers towards each other and continue the comparison.
- If they are not equal, the string is not a palindrome.
- If the pointers cross each other without finding any unequal characters, the string is a palindrome.

This approach ensures that we only traverse the string once, achieving O(n) time complexity, and we use only a few extra variables, achieving O(1) space complexity.

Here is a step-by-step breakdown of the algorithm:

- Initialize two pointers,
`i`

at the start (0) and`j`

at the end (n-1) of the string. - While
`i < j`

:- Check if
`s[i] != s[j]`

. If true, return`false`

. - Increment
`i`

and decrement`j`

.

- Check if
- If the loop completes without returning
`false`

, return`true`

.

```
public class PalindromeCheck {
public static boolean isPalindrome(String s) {
// Initialize two pointers
int i = 0;
int j = s.length() - 1;
// Traverse the string from both ends
while (i < j) {
// If characters at i and j are not equal, return false
if (s.charAt(i) != s.charAt(j)) {
return false;
}
// Move the pointers towards the center
i++;
j--;
}
// If no mismatch found, return true
return true;
}
public static void main(String[] args) {
// Test cases
System.out.println(isPalindrome("madam racecar madam")); // true
System.out.println(isPalindrome("abcbx")); // false
}
}
```

**Time Complexity:** O(n), where n is the length of the string. We traverse the string once.

**Space Complexity:** O(1), as we use only a few extra variables.

Consider the following edge cases:

- Empty string: Should return
`true`

. - Single character string: Should return
`true`

. - Strings with special characters and spaces: Ensure the algorithm handles them correctly.

Examples:

Input:""Output:true

Input:"a"Output:true

To test the solution comprehensively, consider a variety of test cases:

- Simple palindromes: "madam", "racecar"
- Non-palindromes: "hello", "world"
- Edge cases: "", "a", "ab"
- Strings with spaces and special characters: "A man, a plan, a canal, Panama"

Use a testing framework like JUnit to automate the testing process.

When approaching such problems:

- Understand the problem requirements and constraints.
- Think about different approaches and their trade-offs.
- Start with a simple solution and then optimize it.
- Practice similar problems to improve problem-solving skills.

In this blog post, we discussed how to determine if a string is a palindrome using a two-pointer technique. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for coding interviews.