Palindrome Check

Beginner Problems Basic Strings Easy

Palindrome checking algorithms, similar to the problem statement, have interesting implications in the development of DNA sequence analysis tools used in Bioinformatics
Since DNA can be read in both directions, identifying palindromic sequences is a key in the detection of special genetic markers called Restriction sites, essential in Genetic Engineering
Even simple programming challenges have enormous potential in real world applications!

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:

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.

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.

Input : s = "aabbccbbaa"

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/4m2dT7nBZsK/?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:

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:

Initialize two pointers: one at the beginning (`left`) and one at the end (`right`) of the string.
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.
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.

Dry Run

Solution

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;
}
 class Solution {
    // Function to check if a given string is a palindrome
    public boolean 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.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;   
            right--;  
        }
        return true; 
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String str = "racecar";  

        if (solution.palindromeCheck(str)) {
            System.out.println(str + " is a palindrome.");
        } else {
            System.out.println(str + " is not a palindrome.");
        }
    }
}
class Solution:
    # Function to check if a given string is a palindrome
    def palindromeCheck(self, s):
        left = 0               
        right = len(s) - 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 += 1  
            right -= 1  
        return True 

if __name__ == "__main__":
    solution = Solution()
    str = "racecar"  

    if solution.palindromeCheck(str):
        print(f"{str} is a palindrome.")
    else:
        print(f"{str} is not a palindrome.")
class Solution {
    // Function to check if a given string is a palindrome
    palindromeCheck(s) {
        let left = 0;            
        let 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;  
    }
}

// Main function to test the palindromeCheck method
function main() {
    const solution = new Solution();
    const str = "racecar";  

    if (solution.palindromeCheck(str)) {
        console.log(`${str} is a palindrome.`);
    } else {
        console.log(`${str} is not a palindrome.`);
    }
}

// Call the main function to demonstrate the functionality
main();

Note: This problem can also be solved by a Recursive Approach

In the recursive approach, the letters at the two ends of the string are compared. If they match, the function is called recursively for the next pair of elements (start+1, end-1) until the start index is greater than or equal to the end index. If at any point the characters differ, return false. If the base condition is reached (start >= end), the string is a palindrome and true is returned.

Complexity Analysis

Time Complexity: O(N), where n is the length of the string.

Space Complexity: O(1), as no extra space is required.

Code

Problem List