Check Palindrome
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/ * Problem: Check Palindrome * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: Check Palindrome using Recursion * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Write a recursive function that checks whether a given string A is a palindrome or not. * * Return 1 if the string A is a palindrome, else return 0. * * Definition: * A palindrome is a string that reads the same forward and backward. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let S be the string A of length N. * Let P(i, j) be a boolean function that returns true if the substring S[i...j] is a palindrome. * * Recurrence Relation: * P(i, j) = (S[i] == S[j]) AND P(i + 1, j - 1) * * Base Cases (Stopping Conditions): * 1. i >= j : True * (Implying we have met in the middle or crossed; single char or empty string is a palindrome). * 2. S[i] != S[j] : False * (Mismatch found, immediate termination). * * --------------------- * 3. Constraints & Optimization * --------------------- * Constraints: * 1 <= |A| <= 50,000 * String A consists only of lowercase letters. * * Complexity Analysis: * Time Complexity: O(N) - Each character is visited once. * Space Complexity: O(N) - Recursion stack depth. * * Critical Note on Recursion Depth: * With |A| up to 50,000, a naive recursive approach will result in a stack depth of N/2 (25,000 frames). * This may trigger a java.lang.StackOverflowError with default JVM stack sizes (-Xss). * While the problem mandates recursion, typical production code would favor an iterative two-pointer approach * to achieve O(1) auxiliary space. * * --------------------- * 4. Input / Output Format * --------------------- * Input: * - A single argument: String A. * * Output: * - Return 1 if A is a palindrome. * - Return 0 otherwise. * * --------------------- * 5. Examples * --------------------- * Input 1: * A = "naman" * Output 1: * 1 * Explanation: "naman" reads the same backward. * * Input 2: * A = "strings" * Output 2: * 0 * Explanation: "strings" backward is "sgnirts", which is not equal to "strings". * * ============================================================================================ */ public class CheckPalindrome { public int solve(String A) { // TODO: Implement solution return 0; } }