Check if string is palindrome or not

Beginner Problems Basic Recursion Easy

Palindrome problems or algorithms are often used in the development of natural language processing technologies, like chatbots and digital assistants
The performance of these technologies significantly depends on their capability of detecting and understanding patterns, including palindromes, in natural language
This helps in analyzing sentences better, understanding contexts, improving user experience, and adding a pinch of humor
For example, a chatbot could be programmed to identify palindromes and respond with a humorous reply when a user inputs a palindromic phrase

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:

Input : s = "hannah"

Output : true

Explanation : The string when reversed is --> "hannah", which is same as original string , so we return true.

Input : s = "aabbaaa"

Output : false

Explanation : The string when reversed is --> "aaabbaa", which is not same as original string, So we return false.

Input : s = "aabbcccdbbaa"

Constraints

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

Company Tags

TCS Cognizant Accenture Infosys Capgemini Wipro IBM HCL Tech Mahindra MindTree

Editorial

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/79UmK6A8u29/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Intuition

Determining whether a string is a palindrome through recursion involves comparing characters from the start and end of the string. If the characters match, the next set of characters is checked recursively, moving inward. This process continues until a mismatch is found, indicating the string is not a palindrome, or until all characters are verified to match, confirming the string reads the same forwards and backwards.

Approach

Start by comparing the first and last characters of the string. If the characters match, move inward by increasing the starting index and decreasing the ending index. Check if the substring between these indices is also a palindrome.
Continue this process until the starting index is greater than or equal to the ending index. If at any point the characters do not match, the string is not a palindrome.
If all the characters are successfully compared and they all match, the string is a palindrome.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    // Method to check if a string is a palindrome
    bool palindromeCheck(string& s) {
        // Start recursion with the whole string
        return isPalindrome(s, 0, s.length() - 1); 
    }

private:
    // Helper method to perform the recursive check
    bool isPalindrome(string& s, int left, int right) {
        // Base Case: If the start index is greater than or equal to the end index, it's a palindrome
        if (left >= right) {
            return true;
        }
        // Check if characters at the current positions are the same
        if (s[left] != s[right]) {
            return false; // Characters do not match, so it's not a palindrome
        }
        // Recur for the next set of characters
        return isPalindrome(s, left + 1, right - 1);
    }
};

// Main method to test the palindromeCheck function
int main() {
    Solution solution;
    cout << boolalpha; // Print bool values as true/false
    cout << solution.palindromeCheck("hannah") << endl; // Output: true
    cout << solution.palindromeCheck("aabbaaa") << endl; // Output: false
    cout << solution.palindromeCheck("aba") << endl; // Output: true
    return 0;
}
class Solution {
    // Method to check if a string is a palindrome
    public boolean palindromeCheck(String s) {
        // Start recursion with the whole string
        return isPalindrome(s, 0, s.length() - 1); 
    }

    // Helper method to perform the recursive check
    private boolean isPalindrome(String s, int left, int right) {
        // Base Case: If the start index is greater than or equal to the end index, it's a palindrome
        if (left >= right) {
            return true;
        }
        // Check if characters at the current positions are the same
        if (s.charAt(left) != s.charAt(right)) {
            return false; // Characters do not match, so it's not a palindrome
        }
        // Recur for the next set of characters
        return isPalindrome(s, left + 1, right - 1);
    }

    // Main method to test the palindromeCheck function
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.palindromeCheck("hannah")); // Output: true
        System.out.println(solution.palindromeCheck("aabbaaa")); // Output: false
        System.out.println(solution.palindromeCheck("aba")); // Output: true
    }
}
class Solution:
    def palindromeCheck(self, s: str) -> bool:
        # Call the recursive helper method with initial indices
        return self.isPalindrome(s, 0, len(s) - 1)
    
    def isPalindrome(self, s: str, left: int, right: int) -> bool:
        # Base Case: If the start index is greater than or equal to the end index
        if left >= right:
            return True
        # Check if characters at the current positions are the same
        if s[left] != s[right]:
            return False  # Characters do not match, so it's not a palindrome
        # Recur for the next set of characters
        return self.isPalindrome(s, left + 1, right - 1)
    
# Main method to test the palindromeCheck function
if __name__ == "__main__":
    solution = Solution()
    print(solution.palindromeCheck("hannah"))  # Output: True
    print(solution.palindromeCheck("aabbaaa"))  # Output: False
    print(solution.palindromeCheck("aba"))      # Output: True
class Solution {
    // Method to check if a string is a palindrome
    palindromeCheck(s) {
        return this.isPalindrome(s, 0, s.length - 1); // Start recursion with the whole string
    }

    // Helper method to perform the recursive check
    isPalindrome(s, left, right) {
        // Base Case: If the start index is greater than or equal to the end index, it's a palindrome
        if (left >= right) {
            return true;
        }
        // Check if characters at the current positions are the same
        if (s[left] !== s[right]) {
            return false; // Characters do not match, so it's not a palindrome
        }
        // Recur for the next set of characters
        return this.isPalindrome(s, left + 1, right - 1);
    }
}

// Main method to test the palindromeCheck function
function main() {
    const solution = new Solution();
    console.log(solution.palindromeCheck("hannah"));  // Output: true
    console.log(solution.palindromeCheck("aabbaaa"));  // Output: false
    console.log(solution.palindromeCheck("aba"));      // Output: true
}

main(); // Call the main method to run the tests

Complexity Analysis

Time Complexity : O(N) – A single pass through the string with recursive calls, where n is the length of the string.

Space Complexity: O(N) – Due to the recursion stack that grows with the length of the string.

Code

Problem List