Discussion on 'Palindromic Strings' (Problem from Hacker Earth)

To See All Articles About Technology: Index of Lessons in Technology

Try it out

Problem
You have been given a String S. You need to find and print whether this string is a palindrome or not. If yes, print "YES" (without quotes), else print "NO" (without quotes).

Input Format
The first and only line of input contains the String S. The String shall consist of lowercase English alphabets only.

Output Format
Print the required answer on a single line.

Constraints 
1 <= len(S) <= 100

Note
String S consists of lowercase English Alphabets only.

Sample Input
aba
Sample Output
YES
Time Limit: 1
Memory Limit: 256
Source Limit:

Psuedo Code

I would propose two approaches to handling this:

Approach 1

Using indexing [::-1] to reverse the string and checking if matches the original string.

Approach 2

Using recursion. It is based on the fact that a string S of length N would be palindrome then all the substrings S[1:N-1], S[2:N-2],...,S[X, N-X] would also be palindrome. The idea for code would be (to take out first and last characters of the string and check if the resultant substring is a palindrome) and do these two thing recursively.

Critique this psuedo code.

Your proposed pseudocode outlines two solid approaches to checking whether a string is a palindrome. Here's a critique and comparison of both:

---

✅ Approach 1: Reverse and Compare

Pseudocode Summary:

• Reverse the string.

• Compare it with the original.

• If equal → "YES", else → "NO".

✅ Pros:

• Simple & clean: Very readable and requires only a single line in most programming languages.

• Efficient: Time complexity is O(N) and no unnecessary recursion or iteration beyond what's required.

• Best for constraints: Since len(S) ≤ 100, this is highly optimal and safe to use.

❌ Cons:

• Memory usage: Creates a reversed copy of the string, so uses O(N) extra space.

Verdict:

Best option for this problem due to simplicity and efficiency.

---

✅ Approach 2: Recursive Check

Pseudocode Summary:

• If first and last characters are equal, recursively check the substring in between.

• Base case: If the string length is 0 or 1 → return "YES".

✅ Pros:

• Demonstrates deeper thinking: Good for interviews or showing understanding of recursion.

• Elegant: Reflects the recursive structure of the palindrome definition.

❌ Cons:

• Less efficient: Recursive calls add function call overhead.

• Stack overflow risk: For larger inputs (though len ≤ 100 is safe here).

• Overkill: Too much machinery for a very simple check.

Verdict:

Nice to know for academic interest, but not preferred in real-world scenarios unless recursion is specifically required.

---

✅ Final Suggestion

If you’re writing production code or competitive programming solutions: Go with Approach 1.

If you're preparing for interviews and want to impress with recursion skills: Show Approach 2 as a follow-up, but note that it's not the most optimal.

Would you like both approaches written in actual code for comparison?

Yes, please share a more optimal solution.

Sure! Here's a more optimal (and standard) solution to check if a string is a palindrome — using the reverse-and-compare method, which is both simple and efficient.

---

✅ Optimal Solution (Reverse and Compare)

python
S = input().strip()

if S == S[::-1]:
    print("YES")
else:
    print("NO")

---

🔍 Explanation:

• S[::-1] creates a reversed version of the string.

• If the original and reversed strings are the same, it's a palindrome.

• Time complexity: O(N)

• Space complexity: O(N) (due to the reversed copy)

---

✅ Alternative: Two-Pointer Approach (Saves Memory)

If you want O(1) space, you can avoid reversing the string:

python
S = input().strip()
is_palindrome = True

for i in range(len(S) // 2):
    if S[i] != S[-(i + 1)]:
        is_palindrome = False
        break

print("YES" if is_palindrome else "NO")

---

🔍 Why This is More Optimal:

• Uses only a flag and a loop.

• No reversed copy of the string.

• Time complexity: O(N), Space complexity: O(1)

This version is better if memory is a concern or you want to show detailed logic (e.g. in interviews).

Let me know if you'd like to see the recursive version too!