পাইথনে টার্গেট থেকে বড় সবচেয়ে ছোট অক্ষর (Find Smallest Letter Greater Than Target)

সমস্যা বিবরণ

সর্ট করা ছোট হাতের অক্ষরের লিস্ট এবং একটি টার্গেট অক্ষর দেওয়া থাকে। টার্গেট থেকে বড় সবচেয়ে ছোট অক্ষর খুঁজে বের করুন। লিস্ট রাউন্ড-রবিন (wrap around) — 'z'-এর পর 'a' আসে।

উদাহরণ

letters = ["c","f","j"], target = 'a' → আউটপুট: 'c'

target = 'z', letters = ['a','b'] → আউটপুট: 'a' (wrap around)।

এলগরিদম (বাইনারি সার্চ)

1. l = 0, r = len(letters) - 1।
2. যখন l <= r:
   • mid = (l + r) // 2।
   • যদি letters[mid] > target → r = mid - 1।
   • অন্যথায় → l = mid + 1।
3. return letters[l % len(letters)] (wrap around হ্যান্ডল করে)।

পাইথন বাস্তবায়ন

class Solution:
    def nextGreatestLetter(self, letters, target):
        l, r = 0, len(letters) - 1
        while l <= r:
            mid = (l + r) // 2
            if letters[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        return letters[l % len(letters)]

ob = Solution()
print(ob.nextGreatestLetter(["c","f","j"], "a"))  # c
print(ob.nextGreatestLetter(["a","b"], "z"))      # a

ইনপুট / আউটপুট

ইনপুট: ["c","f","j"], "a"
আউটপুট: c