Given a string S consisting of N characters of the English alphabet, the task is to check if the given string is a palindrome. If the given string is a palindrome, then print “Yes“. Otherwise, print “No“.
Note: A string is said to be palindrome if the reverse of the string is the same as the string.
Examples:
Input: S = “ABCDCBA” Output: Yes Explanation: The reverse of the given string is equal to the (ABCDCBA) which is equal to the given string. Therefore, the given string is palindrome. Input: S = “GeeksforGeeks” Output: No Explanation: The reverse of the given string is equal to the (skeeGrofskeeG) which is not equal to the given string. Therefore, the given string is not a palindrome.
Naive Approach: The simplest approach to use the inbuilt reverse function in the STL. Follow the steps below to solve the problem:
Below is the implementation of the above approach:
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check whether // the string is palindrome string isPalindrome(string S) { // Stores the reverse of the // string S string P = S; // Reverse the string P reverse(P.begin(), P.end()); // If S is equal to P if (S == P) { // Return "Yes" return "Yes"; } // Otherwise else { // return "No" return "No"; } } // Driver Code int main() { string S = "ABCDCBA"; cout << isPalindrome(S); return 0; }
Output
Yes
Efficient Approach: The above approach can be optimized in space complexity by traversing the string and checking whether the character at ith index is equal to the character at the (N-i-1)th index for every index in the range [0, N/2]. Follow the steps below to solve the problem:
Below is the implementation of the above approach:
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check whether string // is palindrome string isPalindrome(string S) { // Iterate over the range [0, N/2] for (int i = 0; i < S.length() / 2; i++) { // If S[i] is not equal to // the S[N-i-1] if (S[i] != S[S.length() - i - 1]) { // Return No return "No"; } } // Return "Yes" return "Yes"; } // Driver Code int main() { string S = "ABCDCBA"; cout << isPalindrome(S); return 0; }
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)