Problem Statement

You are given a string s. Return true if the string is palindrome, otherwise false.

A string is called palindrome if it reads the same forward and backward.

Examples

Example 1

Input : s = "hannah"

Output : true

Explanation : The given string when read backward is -> "hannah", which is same as when read forward.

Hence answer is true.

Example 2

Input : s = "aabbaaa"
Output : false

Explanation : The given string when read backward is -> "aaabbaa", which is not same as when read forward.

Hence answer is false.

Constraints

1 <= s.length <= 105
s consist of only uppercase and lowercase English characters.

Approaches

1️⃣ Check by comparing left and right end

Intuition:

To determine if a string is a palindrome, that is, reads the same backwards as forwards, begin by comparing the first and last characters. If they match, proceed by moving inward from both ends and comparing the subsequent pairs of characters. This process is repeated, gradually converging towards the center of the string. If all character pairs match throughout this process, the string is confirmed to be a palindrome. This method effectively checks for symmetry by comparing characters from both ends toward the center.

Approach:

1. Initialize two pointers: one at the beginning (`left`) and one at the end (`right`) of the string.
2. Run a for loop till half the length of the string to compare the first and last characters. If they are not equal, return false.
3. Move both pointers inward (increment `left` and decrement `right`) and continue the comparison. If the loop completes without finding unequal characters, the string is a palindrome and returns true.

Code:

class Solution {
    public:
        // Function to check if a given string is a palindrome
        bool palindromeCheck(string& s) {
            int left = 0;             
            int right = s.length() - 1; 

            // Iterate while start pointer is less than  end pointer
            while (left < right) {
                // If characters don't match, it's not a palindrome
                if (s[left] != s[right]) {
                    return false;
                }
                left++;   
                right--;  
            }
            return true;  
        }
};

int main() {
    Solution solution;
    string str = "racecar";  

    if (solution.palindromeCheck(str)) {
        cout << str << " is a palindrome." << endl;
    } else {
        cout << str << " is not a palindrome." << endl;
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N), where n is the length of the string.
• Space Complexity: O(1), as no extra space is required.