পাইথনে O(1) অতিরিক্ত স্পেসে স্ট্রিংয়ের অক্ষরগুলো প্যালিনড্রোম বানায় কিনা

একটি স্ট্রিং s দেওয়া আছে যেটিতে ছোট হাতের অক্ষর, সংখ্যা, বিশেষ ক্যারেক্টার থাকতে পারে। শুধু অক্ষরগুলো নিয়ে প্যালিনড্রোম বানায় কিনা যাচাই করতে হবে, অতিরিক্ত স্পেস ব্যবহার ছাড়া।

উদাহরণ

ইনপুট: s = "ra$5ce58car"

আউটপুট: True

ব্যাখ্যা: অক্ষরগুলো "racecar" বানায় যা প্যালিনড্রোম।

অ্যালগরিদম

1. দুটি পয়েন্টার left এবং right ব্যবহার করুন।
2. first_letter_index: বাম থেকে ডান প্রথম অক্ষর খুঁজুন।
3. last_letter_index: ডান থেকে বাম শেষ অক্ষর খুঁজুন।
4. অক্ষরগুলো মিলিয়ে যান, না মিললে False।

উদাহরণ কোড

def first_letter_index(s, left, right):
    index = -1
    for i in range(left, right + 1):
        if 'a' <= s[i] <= 'z':
            index = i
            break
    return index

def last_letter_index(s, left, right):
    index = -1
    for i in range(left, right - 1, -1):
        if 'a' <= s[i] <= 'z':
            index = i
            break
    return index

def solve(s):
    left = 0
    right = len(s) - 1
    flag = True
    for _ in range(len(s)):
        left = first_letter_index(s, left, right)
        right = last_letter_index(s, right, left)
        if right < 0 or left < 0:
            break
        if s[left] == s[right]:
            left += 1
            right -= 1
            continue
        flag = False
        break
    return flag

s = "ra$5ce58car"
print(solve(s))  # Output: True

ইনপুট

"ra$5ce58car"

আউটপুট

True