Recursion & BacktrackingEasyO(n) time · O(n) space

Check if String is Palindrome

Mahabharata — The Mirror Verse — A Shloka That Reads the Same Forward and Backward

आगे पीछे — समान। प्रथम अंतिम मिलते हैं — मध्य तक यही है सत्य॥

*Forward backward — the same. First and last meet — this truth holds to the center.*

The Story

Check if a string is a palindrome using recursion.

For `s="racecar"`: true. For `s="hello"`: false.

**Recursive approach:** - Base case: if i >= j (crossed or met in middle) → true (empty or single char is palindrome) - Recursive case: s[i] == s[j] AND isPalindrome(s, i+1, j-1)

```java boolean isPalindrome(String s, int i, int j) { if (i >= j) return true; // Base: empty or single char if (s.charAt(i) != s.charAt(j)) return false; // Mismatch return isPalindrome(s, i+1, j-1); // Recurse inward } // Call: isPalindrome(s, 0, s.length()-1) ```

Trace "racecar": - isPal(0,6): r==r ✓ → isPal(1,5) - isPal(1,5): a==a ✓ → isPal(2,4) - isPal(2,4): c==c ✓ → isPal(3,3) - isPal(3,3): 3>=3 (base) → true - All return true ✓

Trace "hello": - isPal(0,4): h≠o → false immediately ✓

**The recursion pattern:** At each level, we handle one pair (outer characters) and delegate the inner string to the next recursive call. This is the "shrink problem" pattern: make it smaller, recurse, combine.

The Two-Pointer Iterative Check

Two pointers from both ends meeting in the middle. O(n) time, O(1) space.

java

boolean isPalindromeIterative(String s) {
    int i=0, j=s.length()-1;
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) return false;
        i++; j--;
    }
    return true;
}

The Inward-Peeling Recursive Wisdom

Base: i>=j → true. Check s[i]==s[j], then recurse(i+1, j-1). Short-circuits on first mismatch.

java

boolean isPalindrome(String s, int i, int j) {
    if (i >= j) return true;
    if (s.charAt(i) != s.charAt(j)) return false;
    return isPalindrome(s, i + 1, j - 1);
}

Step-by-Step Walkthrough

"a"
isPal(0,0): 0>=0 → true ✅
""
isPal(0,-1): 0>=-1 → true ✅

Deep Insight

**Recursion structure:** The call stack grows to depth n/2. Each frame handles one pair. This is O(n) space due to the call stack.

**The iterative version uses O(1) space** — same logic but without the call stack overhead. In practice, prefer iterative for large strings.

**Short-circuit optimization:** The `if (s.charAt(i) != s.charAt(j)) return false` before the recursive call ensures we don't make unnecessary recursive calls once a mismatch is found. Without this, we'd still recurse (and always hit the mismatch somewhere), but it's cleaner.

**Pattern:** This 'shrink from both ends' recursion is the basis for many string DP problems (longest palindromic subsequence, etc.).

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n)	O(1)	Two-pointer iterative
Optimal	O(n)	O(n)	Recursive call stack depth n/2

Pattern Recognition

✅ Palindrome check → shrink from both ends
✅ Base: i>=j → true
✅ Recursive: check s[i]==s[j] then isPal(i+1,j-1)
✅ Iterative (O(1) space) is usually preferred

**LeetCode Trigger Phrases:**
→ "palindrome string" check
→ Shrink-from-both-ends recursion
→ Foundation for palindromic DP problems

Bhagavad Gita 6.19

यथा दीपो निवातस्थो नेङ्गते सोपमा स्मृता। योगिनो यतचित्तस्य युञ्जतो योगमात्मनः॥

As a lamp in a windless place does not flicker — that is the classic metaphor for the yogi of controlled mind engaged in yoga.

Connection: A palindrome is the same from both directions — symmetric, unchanged by reversal, like a flame undisturbed by wind. The recursive check peels away the outer layers, verifying symmetry at each depth until reaching the unmoving center. Like the still lamp and the still mind, the palindrome represents perfect symmetry — reading the same forward and backward, the outer forms a perfect mirror of itself, all the way to the silent center.