7.StringPalin.md

📘 Checking if a String Is a Palindrome Using Recursion

🧾 Problem Statement

Goal: Given a string s, determine recursively whether it reads the same forward and backward (i.e., is a palindrome).

---

🔎 Examples

Input	Output	Explanation
"racecar"	True	"racecar" reversed is "racecar".
"Madam"	False (case-sensitive)
"A man, a plan, a canal, Panama!" (after cleaning)	True (ignoring non-letters & case)

Note: The simplest version below is case-sensitive and checks all characters. You can extend it to ignore punctuation and case by preprocessing the string.

---

💡 Approach

1. Two-Pointer Technique:

   • Compare the first and last characters.
   • If they match, recurse on the substring excluding those characters.
   • If they differ, terminate with false.

2. Base Cases:

   • If left >= right, we’ve checked all pairs → true.
   • If at any point s[left] != s[right] → false.

---

🔁 Algorithm

FUNCTION isPalindromeRecursive(s, left, right):
    IF left >= right:
        RETURN true   // Checked all character pairs

    IF s[left] ≠ s[right]:
        RETURN false  // Mismatch found

    // Recurse inward
    RETURN isPalindromeRecursive(s, left + 1, right - 1)

Wrapper Function:

FUNCTION isPalindrome(s):
    RETURN isPalindromeRecursive(s, 0, s.length() - 1)

---

💾 C++ Code Snippet

#include <iostream>
#include <string>
using namespace std;

// Recursive helper: checks s[left..right]
bool isPalindromeRecursive(const string& s, int left, int right) {
    // Base case: zero or one character left
    if (left >= right) {
        return true;
    }
    // Mismatch case
    if (s[left] != s[right]) {
        return false;
    }
    // Recurse inward
    return isPalindromeRecursive(s, left + 1, right - 1);
}

// Public API: checks entire string
bool isPalindrome(const string& s) {
    return isPalindromeRecursive(s, 0, static_cast<int>(s.length()) - 1);
}

int main() {
    string s;
    getline(cin, s);

    if (isPalindrome(s)) {
        cout << '"' << s << "\" is a palindrome.\n";
    } else {
        cout << '"' << s << "\" is not a palindrome.\n";
    }
    return 0;
}

Example Run:

Input:  racecar  
Output: "racecar" is a palindrome.

Input:  hello
Output: "hello" is not a palindrome.

---

🧮 Dry Run

For s = "noon":

Call	left	right	Comparison	Result
isPalindromeRecursive("noon",0,3)	0	3	s[0]='n' vs s[3]='n'	match → recurse
isPalindromeRecursive("noon",1,2)	1	2	s[1]='o' vs s[2]='o'	match → recurse
isPalindromeRecursive("noon",2,1)	2	1	left ≥ right	base → return true

---

📈 Complexity Analysis

Metric	Value
🕒 Time Complexity	O(n)
🧠 Space Complexity	O(n) (recursion stack)

• Time: Each recursive call compares one pair → ~n/2 calls → O(n).
• Space: Call stack depth ~n/2 → O(n).

---

📎 Notes & Enhancements

• Case-Insensitive & Alphanumeric Only:

  • Preprocess by building a cleaned string:

    string clean;
    for (char c : s) {
        if (isalnum(c)) 
            clean += tolower(c);
    }

  • Then call isPalindrome(clean).

• Iterative Alternative:

  bool isPalindromeIter(const string& s) {
      int l = 0, r = s.size() - 1;
      while (l < r) {
          if (s[l++] != s[r--]) return false;
      }
      return true;
  }

  • Uses O(1) auxiliary space.

• Stack Overflow Warning:

  • Very long strings could exhaust the recursion stack. In such cases, prefer the iterative method.

• Edge Cases:

  • Empty string ("") → true.
  • Single character → true.

---